<题目链接>
题目大意：
给你一棵树，进行q次询问，每次询问问你以这个点为根的子树的重心是哪个节点。
解题分析：
首先做本题需要知道一个结论：以x为根的子树的重心，一定在以x的重儿子为根的子树的重心与x的连线上，所以我们就先处理出所有点的重儿子，之后再求解每个子树的重心。重心的求法就是，从该节点重儿子为根的子树的重心开始，判断是否符合条件，如果不符合条件，就一直向上枚举，直到找到符合重心判定条件的节点为止。 这篇博客讲得很好 >>>
#include <bits/stdc++.h> using namespace std; const int N = 3e5+5; int n,q,cnt; int head[N],sz[N],ans[N],son[N],fa[N]; struct Edge{ int to,nxt; }e[N]; inline void add(int u,int v){ e[++cnt]=Edge{v,head[u]};head[u]=cnt; } void dfs(int u){ son[u]=0,sz[u]=1; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; dfs(v); sz[u]+=sz[v]; if(sz[v]>sz[son[u]])son[u]=v; } if(sz[u]==1){ ans[u]=u;return; } int g=ans[son[u]]; //g为以u的重儿子为根的树的重心 while(true){ bool fp=true; if(sz[son[g]]>sz[u]/2)fp=false; //判断son[g]的子节点方向是否符合要求 if(sz[u]-sz[g]>sz[u]/2)fp=false; //判断son[g]的父节点方向是否符合要求 if(fp){ ans[u]=g;return; } g=fa[g]; //沿着father一直向上枚举,这里根据的就是一个结论，即以u根的子树的重心，一定在以这个节点的重儿子为根的子树的重心到u的连线上 } } int main(){ scanf("%d%d",&n,&q); for(int i=2;i<=n;i++){ scanf("%d",&fa[i]); add(fa[i],i); } dfs(1); while(q--){ int rt;scanf("%d",&rt); printf("%d ",ans[rt]); //ans[rt]表示以rt为根的子树的重心 } }