树的重心

树 $T$ 中的结点 $v$ 是它的重心，当且仅当以下任意一条成立：

无根树版本

1. 在树中删去结点 $v$ 后，得到的图 $T\setminus\{v\}$ 中每个连通分量的大小均不超过原树结点数的一半．

2. 在所有删去某个结点后得到的最大连通分量大小中，删去结点 $v$ 时所得到的值最小．

3. 树中所有结点到某个结点的距离和中，到结点 $v$ 的距离和最小．

有根树版本

1. 当树以结点 $v$ 为根时，任一真子树的大小均不超过原树结点数的一半．
2. 在所有以某个结点为根时的最大真子树大小中，以结点 $v$ 为根时所得到的值最小．
3. 在所有以某个结点为根时所有结点的深度和中，以结点 $v$ 为根时深度和最小．

首先，引入一些记号．有根树和无根树两个版本的表述显然是等价的．定义 $W(x)=\max_{u\sim x}|T_u^{(x)}|$，其中，$u\sim x$ 表示 $u$ 和 $x$ 相邻．定义 $S(x)=\sum_{u\in T}d(u,x)$，其中，$d(u,x)$ 表示结点 $u$ 和 $x$ 之间的距离．那么，定义 1 相当于要求 $W(v)\le |T|/2$，定义 2 相当于要求 $v\in\arg\min_{x\in T}W(x)$，定义 3 相当于要求 $v\in\arg\min_{x\in T}S(x)$．需要证明的是，这三个条件是等价的．

将 $S(x)$ 理解为以 $x$ 为根时的结点深度和，考虑它在树根从结点 $v$ 换为相邻结点 $u$ 时发生的变化．注意到，在树中删去边 $(v,u)$ 后，得到的两个连通分量分别是子树 $T_v^{(u)}$ 和 $T_u^{(v)}$．在换根前后，子树 $T_v^{(u)}$ 中每个结点深度都增加 $1$，子树 $T_u^{(v)}$ 中每个结点深度都减少 $1$，所以，深度和的变化为

所以，定义 1 的条件相当于要求 $\Delta S_{v\to u}\le 0$ 对 $v$ 的所有相邻结点 $u$ 都成立，也就是说，$v$ 是 $S(x)$ 的极小值点．

转而设 $v$ 是 $S(x)$ 的（一个）最小值点（即定义 3），它必然存在，且一定是极小值点．考虑以 $v$ 为根的有根树 $T^{(v)}$．设 $u\neq v$ 是一个非根结点，且从 $v$ 到 $u$ 的有向路径上，结点 $v$ 的后一个结点为 $y$（可能就是 $u$），结点 $u$ 的前一个结点为 $x$（可能就是 $v$）．那么，因为 $T_u^{(x)}\subseteq T_y^{(v)}$，所以有

其中，最后一步用到 $v$ 是 $S(x)$ 的极小值点这一事实．此时，有两种情形：

• 存在结点 $u$ 使得 $2|T_x^{(u)}|=|T|$ 成立．此时，根据上述不等式，必然有 $(x,u)=(v,y)$，且 $|T_v^{(u)}|=|T_{u}^{(v)}| = |T|/2$．也就是说，使得等式成立的结点 $u$ 只能有一个，且它必然与 $v$ 相邻．此时，对于所有其他结点 $u'\neq u,v$，必然存在 $x'\sim u'$ 使得 $|T_{x'}^{(u')}| > |T|/2$ 成立．满足条件 1 的结点集合为 $\{v,u\}$．

  注意到，删去任何结点时，得到的连通分量大小之和总是 $|T|-1$，所以，只要有一个连通分量大小不小于 $|T|/2$，它就必然是最大连通分量．因此，对于这种情形，$W(v)=W(u)=|T|/2$，且对于所有 $u'\neq u,v$ 都有 $W(u') > |T|/2$．因此，满足条件 2 的结点集合为 $\arg\min W(x) = \{v,u\}$．

  又因为 $\Delta S_{v\to u} = 0$，所以 $S(v)=S(u)$．因为 $v$ 是最小值点，$u$ 也一定是最小值点．而对于 $u'\neq u,v$ 都存在 $x'\sim u'$ 使得 $|T_{x'}^{(u')}| > |T|/2$，这违反了极小值点需要满足的条件，所以，$u'$ 一定也不是最小值点．因此，满足条件 3 的结点集合为 $\arg\min S(x) = \{v,u\}$．

• 不存在结点 $u$ 使得 $2|T_x^{(u)}|=|T|$ 成立．此时，对于所有结点 $u\neq v$，都存在结点 $x\sim u$ 使得 $|T_x^{(u)}| > |T|/2$．重复前文分析可知，对于所有结点 $u\neq v$，都有 $W(u) > |T|/2$，且 $u$ 不是 $S(x)$ 的极小值点．因此，满足条件 1 的结点只有 $v$，且 $\arg\min W(x)=\arg\min S(x) = \{v\}$．

无论在哪一情形中，满足三个条件的集合都是相同的．这就证明了三个定义是等价的．

1. 树的重心如果不唯一，则恰有两个．这两个重心相邻．而且，删去它们的连边后，树将变为两个大小相同的连通分量．
2. 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离．
3. 把两棵树通过一条边相连得到一棵新的树，那么新树的重心在连接原来两棵树的重心的路径上．
4. 一棵有根树的重心一定在根结点所在的重链上．一棵树的重心一定是该树根结点重子结点对应子树的重心的祖先．

性质 1 可以从对重心等价定义的证明中得到．

性质 2 只需要考虑添加一个叶子结点的情形．这进一步分为两种情形：

• 树 $T$ 只有一个重心 $v$．设 $x$ 为新添加的叶子结点，且在新树中删去结点 $v$ 得到的图 $T\cup\{x\}\setminus\{v\}$ 中，$x$ 所在连通分量为 $B\cup\{x\}$．因为 $v$ 是树 $T$ 的唯一重心，所以 $2|B| < |T|$，也就是 $2|B|+1\le |T|$．进而，有

  $$2|B\cup\{x\}| = 2(|B|+1) \le |T| + 1 = |T\cup\{x\}|.$$

  因此，$v$ 仍然是新树 $T\cup\{x\}$ 的重心．即使新树的重心不唯一，它也必然是 $v$ 的相邻结点．因此，重心至多移动一条边．

• 树 $T$ 有两个重心 $u,v$．此时，删去 $(u,v)$ 得到的两个连通分量 $T_u^{(v)}$ 和 $T_v^{(u)}$ 大小相等，均为 $|T|/2$．不妨设新添加的叶子结点 $x$ 连接在 $v$ 所在的连通分量 $T_v^{(u)}$ 上．那么，因为

  $$|T_v^{(u)}\cup\{x\}| = |T|/2 + 1 > (|T|+1)/2 = |T\cup\{x\}|/2,$$

  所以 $u$ 不再是新树的重心．反过来，因为删去 $v$ 后，仍然有大小为 $|T|/2$ 的连通分量 $T_u^{(v)}$，而其他连通分量的大小之和为

  $$|T\cup\{x\}| - 1 - |T_u^{(v)}| = |T|/2 \le |T_u^{(v)}|,$$

  所以，$v$ 仍然是新树的重心．因为新树的结点数是奇数，重心必然唯一．所以，重心也至多移动一条边．

总结两种情形的分析可以发现，新树的重心一定在旧树的重心与新添加的叶子结点的路径上．

性质 3 可以通过归纳法说明．设 $T$ 和 $T'$ 连接时，新添加的边为 $(x,y)$，且 $x\in T,y\in T'$．不妨设新树的（一个）重心在 $T$ 中．考虑从树 $T$ 开始，将树 $T'$ 中结点逐一添加为其叶子结点的过程．可以归纳地证明，树的（一个）重心始终在连接树 $T$ 的重心与结点 $x$ 的路径上．归纳起点显然．假设直到某一时刻为止，命题仍然成立．设此时重心为 $v$．由性质 2 的分析可知，新树的重心必然在连接新添加结点和当前重心 $v$ 的路径上，又因为它不会移动到树 $T$ 外，所以，只需要考虑路径与树 $T$ 的公共部分，即连接当前重心 $v$ 和结点 $x$ 的路径上．根据归纳假设，$v$ 就在连接树 $T$ 的重心和结点 $x$ 的路径上，所以，新树重心也必然在连接当前重心 $v$ 和结点 $x$ 的路径上．由归纳法可知，命题成立．

性质 4 只需要结合 重链剖分性质 即可说明．设树 $T$ 的（一个）重心为 $v$．结点 $v$ 是根结点时，命题显然成立．下面设 $v$ 是非根结点，$u$ 是它的父结点．因为 $|T_u^{(v)}| \le |T|/2$，所以，$v$ 所在子树大小至少是 $|T|/2$．但是，只要它到根结点的路径上经过一次轻边，它所在子树大小将严格小于 $|T|/2$，矛盾．所以，它必然在根结点所在重链上．进而，根据重链的定义，根结点重子结点对应子树中根结点所在重链就是原树中根结点所在重链的一部分；而且，根据性质 3，在重子结点对应子树上添加重子结点及其所有轻子结点对应子树后，重心位置将沿着当前重心和根结点路径移动，所以新重心必然是旧重心的祖先．

根据性质 3，对于一棵以点 $u$ 为根的子树，其重心一定在所有以 $u$ 的直接子结点为根的子树的重心到点 $u$ 的路径上．

类似于上文提到的 DFS 求重心方法，对于每棵以结点 $u$ 为根的子树，先求出所有以其直接子结点为根的子树的重心（叶子结点的重心是其本身），然后向上判断路径上的结点是不是重心即可．

在 $O(n)$ 时间内可以求出所有子树的重心．

#include <iostream>
#include <vector>
using namespace std;

constexpr int N = 3e5 + 5;

int n, q;  // 点数，询问数
int fa[N];
vector<int> son[N];
int siz[N],     // 子树大小
    ans[N],     // 以节点 u 为根的子树重心是 ans[u]
    weight[N];  // 节点重量（不包括向上的子树）

void dfs(int u) {
  siz[u] = 1, ans[u] = u;
  for (int v : son[u]) {
    dfs(v);
    siz[u] += siz[v];
    weight[u] = max(weight[u], siz[v]);
  }
  for (int v : son[u]) {
    int p = ans[v];
    while (p != u) {
      if (max(weight[p], siz[u] - siz[p]) <= siz[u] / 2) {
        ans[u] = p;
        break;
      } else
        p = fa[p];
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> q;
  for (int v = 2; v <= n; v++) cin >> fa[v], son[fa[v]].push_back(v);
  dfs(1);
  while (q--) {
    int u;
    cin >> u;
    cout << ans[u] << '\n';
  }
  return 0;
}