Codeforces 686D(树的重心+DFS)

Codeforces 686D
题意：给一棵树求每个子树的重心。

几个定理：

1把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。
2把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离
3去掉任意一个重心后，生成的各个块的节点数的最大值一定小于等于原树的节点数除以2。
4以一棵树的重心为根的子树的节点个数，一定大于等于该树节点总数的一半。
5在一棵树的所有子树中，找到某一子树，使得其节点数恰好大于等于原树节点总数一半，那么该子树的根一定是一个重心。(如果该节点不是重心，也就是把它去掉后产生的连通块中至少有一个节点个数大于原树节点个数的一半。)

这里用定理1、3

对于当前一个子树求重心，他的重心在他的最大子树的重心和子树的根的路径上(定理1)。所以 DFS 即可。
判断路径上是否是重心：判断整个子树在当前枚举位置断开，生成的两个块的节点数的最大值是否小于等于原树的节点数除以2(定理3)

Codeforces Submission

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n, q, ans[300000 + 5], siz[300000 + 5], fa[300000 + 5];
vector<int> G[300000 + 5];
inline void ins(int x, int y) {G[x].push_back(y), G[y].push_back(x);}
void dfs(int u, int pa) {
    int whw = -1, pos = u;
    fa[u] = pa, siz[u] = 1, ans[u] = u;
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i];
        if (v != pa) {
            dfs(v, u);
            siz[u] += siz[v];
            if (whw < siz[v]) whw = siz[v], pos = v;
        }
    }
    ans[u] = ans[pos];
    while (ans[u] != u && siz[u] - siz[ans[u]] > siz[u] / 2) ans[u] = fa[ans[u]];
    //去掉任意一个重心后，生成的各个块的节点数的最大值一定小于等于原树的节点数除以2
}
void clean() {
    ms(siz, 0);
}
int solve() {
    clean();
    for (int p, i = 2; i <= n; i++) scanf("%d", &p), ins(i, p);
    dfs(1, 0);
    while (q--) {
        int a; scanf("%d", &a);
        printf("%d\n", ans[a]);
    }
    return 0; 
}
int main() {
    scanf("%d%d", &n, &q), solve();
    return 0;
}