来填徐州 M 题的坑了...
M 题题面叙述的就是求子树的重心...
百度百科对树的重心的介绍...
树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。
把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。
一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。
一棵树最多有两个重心，且相邻。
然后还有两个性质，一个是一棵树的重心一定在最大子树的重心到根的路径上。
第二个就是判断是否为重心就是以其为根的所有子树的size都不超过整个树的size的二分之一。
然后就做完了...
#include <bits/stdc++.h> const int N = 3e5 + 7; std::vector<int> vec[N]; int cen[N], sz[N], fa[N], heavy[N], pre[N]; int n, q; bool iscen(int u, int v) { return (sz[u] - sz[v]) * 2 <= sz[u] && heavy[v] * 2 <= sz[u]; } void dfs1(int u, int pre) { fa[u] = pre; sz[u] = 1; for (int v: vec[u]) { dfs1(v, u); sz[u] += sz[v]; heavy[u] = std::max(heavy[u], sz[v]); } } void dfs2(int u) { if (sz[u] == 1) { cen[u] = u; return; } int mx = vec[u][0]; for (int v: vec[u]) { dfs2(v); if (sz[mx] < sz[v]) mx = v; } int c = cen[mx]; while (!iscen(u, c)) c = fa[c]; cen[u] = c; } int main() { scanf("%d%d", &n, &q); for (int i = 2; i <= n; i++) { int u; scanf("%d", &u); vec[u].push_back(i); } dfs1(1, 0); dfs2(1); for (int u; q--; ) { scanf("%d", &u); printf("%d\n", cen[u]); } return 0; }
Codeforces Round #359 (Div. 2) D. Kay and Snowflake
原文：https://www.cnblogs.com/Mrzdtz220/p/11794483.html
