题解 CF685B 【Kay and Snowflake】

**题目描述：给出n个数，n-1个数的父亲节点，共q个询问，求以ai为根节点的子树的重心** $size[i]$表示以i为根节点的子树节点个数， 有树的重心的性质可知，当某节点u的最大子树节点v的size的两倍小于$size[u]$ 该点为重心 即$size[v]*2< size[u]$ 不然暴力往上走，时间复杂度$O(n)$ 上代码 ``` #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,q; const int N=600001; int nxt[N],first[N],go[N],tot,size[N],f[N],ans[N],fa[N]; void add(int x,int y) { nxt[++tot]=first[x]; first[x]=tot; go[tot]=y; } void dfs(int x) { ans[x]=x; size[x]=1; int maxn=0,t=0; for(int i=first[x]; i; i=nxt[i]) { int v=go[i]; dfs(v); size[x]+=size[v]; if(size[v]>maxn) { maxn=size[v]; t=v; } } f[x]=maxn; if(f[x]*2<size[x])ans[x]=x; else { int now=ans[t]; while(fa[now]&&max(f[now],size[x]-size[now])>max(f[fa[now]],size[x]-size[fa[now]]))now=fa[now]; ans[x]=now; } } int main() { cin>>n>>q; for(int i=2; i<=n; i++) { int k; cin>>k; fa[i]=k; add(k,i); } dfs(1); for(int i=1; i<=q; i++) { int k; cin>>k; cout<<ans[k]<<endl; } } ```