http://codeforces.com/contest/686/problem/D
给出q个询问，每次要求询问以x为根的子树中，哪一个点是重心。
树的重心：求以cur为根的子树的重心，就是要找一个点，使得删除这个点后，分开来的零散的子树中，节点数的最大值最小。并且最大值最多也只是son[cur] / 2，因为最坏情况（最难分）也就是一条直线，选中间点就可以了。
例如
询问1的时候，就应该删除3，然后得到4个零散分支，2个大小是1,2个是2。
算法思路：
直观来说，应该是删除那个儿子数最多的那个节点的。 比如上图，3的儿子数最多，所以询问1就删除3了。因为，没理由再分一些节点给最大的那颗子树把，这样只会更坏。
但是却可以把最大的那颗子树分一些节点去另一边，所以优先删除最大的那颗子树的重心，然后判断是否符合要求，不符合就只能暴力往上找了。
判定条件是son[cur] > 2 * son[重心]就不行。
因为这表明son[cur] - son[重心]的值还大于son[cur] / 2
代进去就知道了son[cur] - son[重心] > son[重心]，
假设son[cur] = 2 * son[重心]。那么就是剩下的节点数会大于son[cur] / 2咯。。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 300000 + 20; int ans[maxn]; int son[maxn]; //第u个点有多少个儿子。 int fa[maxn]; //记录第i个点的爸爸是谁 struct node { int u, v, tonext; }e[maxn]; int first[maxn]; int num; void add(int u, int v) { ++num; e[num].u = u; e[num].v = v; e[num].tonext = first[u]; first[u] = num; } void dfs(int cur, int from) { son[cur] = 1; //自己一个 ans[cur] = cur; //叶子节点 int mx = -inf, pos = cur; //以这个点为子树的儿子数最多的那个pos for (int i = first[cur]; i; i = e[i].tonext) { dfs(e[i].v, cur); son[cur] += son[e[i].v]; //加上儿子的节点个数 if (mx < son[e[i].v]) { //不能算自己，只能算儿子的max mx = son[e[i].v]; pos = e[i].v; //儿子数最多的那个节点， } } ans[cur] = ans[pos]; //ans[pos]已经算出来了，ans[pos]的重心 while (son[cur] > 2 * son[ans[cur]]) { ans[cur] = fa[ans[cur]]; //暴力往上找 } } void work() { int n; cin >> n; int q; cin >> q; for (int i = 2; i <= n; ++i) { int x; cin >> x; add(x, i); fa[i] = x; } dfs(1, -1); for (int i = 1; i <= q; ++i) { int x; cin >> x; cout << ans[x] << endl; } } int main() { #ifdef local freopen("data.txt","r",stdin); #endif IOS; work(); return 0; }
重心的定义是：
找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡
(一)
树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。
(二)
把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。
(三)
把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。