树的重心

1. $\Rightarrow$：如果存在一个重心使得某个子树大小 $> \frac{n}{2}$，那么向着这个子树的方向移动一条边，一定能找到一个更优的重心。$\Leftarrow$：当以 $u$ 为根时，如果所有子树大小 $\leq \frac{n}{2}$，那么它的任意邻居 $v$ 不可能比 $u$ 更优，因为以 $v$ 为根时，$u$ 所在子树的大小会 $\geq \frac{n}{2}$。

2. 易证一个和两个的情况，如果有 $3$ 个重心，易证每两个重心之间一定有一条边相连，而这样的话会形成一个大小为 $3$ 的环，不可能是树。

   2.1. 有两个重心意味着有两个大小为 $\frac{n}{2}$ 的子树。

3. 设点 $u$ 到所有其他点的距离为 $d_u$，那么如果存在一个邻居 $v$ 使得 $v$ 所在子树的大小 $> \frac{n}{2}$，那么移动到 $v$ 一定有 $d_v < d_u$（因为贡献的点数量 $> \frac{n}{2}$）。由此可以推出，除了重心以外的点都至少存在一个邻居使得 $d_v$ 更小，可以得出重心的 $d_u$ 最小。

4. WLOG 假设两棵树一大一小，可以看作将小子树一个个作为叶子的加入到大子树上，此时重心会沿着连接的点方向移动。

   

5. 易证。

首先判断重心是不是有 $2$ 个，如果不是，什么也不用干。

如果是，那么设两个重心分别为 $c_1, c_2$，那么只要在 $c_2$ 子树中寻找一个叶子，然后切下来，安给 $c_1$ 即可。

证明：易证 $c_1$ 的其他邻居不可能为新的重心，而 $c_2$ 也不可能为重心，因为 $c_2$ 所在的部分少了一个，所以只有 $c_1$ 变成新的重心了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int T, n;
struct Edge {
    int from, to, nxt;
} edges[maxn<<1];
int head[maxn], ecnt = 1;
void addEdge(int u, int v) {
    Edge e = {u, v, head[u]};
    head[u] = ecnt;
    edges[ecnt++] = e;
}

int sz[maxn];
bool center[maxn];
int c1, c2;
void dfs1(int u, int p) {
    sz[u] = 1;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to;
        if (v == p) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > n/2) center[u] = 0;
    }
    if (n - sz[u] > n/2) center[u] = 0;
}
int c, cp;
// f: forbidden
void dfs2(int u, int p, int f) {
    sz[u] = 1;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to;
        if (v == f || v == p) continue;
        dfs2(v, u, f);
        sz[u] += sz[v];
    }
    if (sz[u] == 1) {
        c = u;
        cp = p;
    }
}

int main() {
    fastio;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i < n; i++) {
            int x,y; cin >> x >> y;
            addEdge(x, y); addEdge(y, x);
        }
        for (int i = 1; i <= n; i++) center[i] = 1;
        dfs1(1, 0);
        c1 = c2 = 0;
        for (int i = 1; i <= n; i++) {
            if (center[i]) {
                if (!c1) c1 = i;
                else c2 = i;
            }
        }
        if (!c2) {
            cout << edges[1].from << " " << edges[1].to << "\n" << edges[1].from << " " << edges[1].to << "\n";
        } else {
            c = cp = 0;
            dfs2(c2, 0, c1);
            cout << c << " " << cp << "\n" << c << " " << c1 << "\n";
        }
        for (int i = 1; i <= n; i++) head[i] = 0, sz[i] = 0;
        ecnt = 1;
    }
}

结论：考虑 $u$ 的子树，它的重心要么是它自己，要么在它重儿子所在子树里。

如果在它重儿子（设为 $v$）里，那么可以看作以 $v$ 为子树，然后加上了一个较小的子树（$u$ 剩下的部分），所以原本重心是 $v$ 的重心，加上了以后，重心会往连接点处移动，所以新的重心一定是 $v$ 的重心的 ancestor。

所以我们可以从下往上处理每个子树的重心，处理到 $u$ 时只要从它的重儿子 $v$ 的重心 $c_v$ 开始，暴力往上跳即可。

可证每个点最多会被跳 $1$ 次，复杂度为 $O(n)$。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;

int n, q;
struct Edge {
    int from, to, nxt;
} edges[maxn<<1];
int head[maxn], ecnt = 1;
void addEdge(int u, int v) {
    Edge e = {u, v, head[u]};
    head[u] = ecnt;
    edges[ecnt++] = e;
}
int sz[maxn], par[maxn], son[maxn], maxsz[maxn], ans[maxn];
void dfs(int u, int p) {
    sz[u] = 1;
    par[u] = p;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to;
        if (v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
        if (maxsz[u] < sz[v]) {
            son[u] = v;
            maxsz[u] = sz[v];
        }
    }
}

void dfs2(int u, int p) {
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to;
        if (v == p) continue;
        dfs2(v, u);
    }
    if (maxsz[u] <= sz[u] / 2) {
        ans[u] = u;
        return;
    } else {
        int c = ans[son[u]];
        while (c != u) {
            if (maxsz[c] <= sz[u] / 2 && sz[u] - sz[c] <= sz[u] / 2) {
                ans[u] = c;
                break;
            } else c = par[c];
        }
    }
}

int main() {
    cin >> n >> q;
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        addEdge(p, i);
        addEdge(i, p);
    }
    dfs(1, 0);
    dfs2(1, 0);
    while (q--) {
        int x; cin >> x; cout << ans[x] << "\n";
    }
}