B. Kay and Snowflake(重心的性质)

$\color{Red}重心定义:去掉重心后,树分成若干个连通块,要使最大连通块最小$

$考虑x为根的树和x的一些儿子y$

$现在已知y为根的子树的重心s,如何递推到x为根的子树?$

$这么想,y子树->s子树的过程中,也就是在y的头上加了x和x的其他儿子$

$也就是如果把s砍掉,头上的那个连通块比以前大$

假如头上那个连通块不是最大的,那位置s为重心一定最优

假如头上的连通块变成最大的,那把s往上跳,最大连通块会变小,答案会变优

所以每次尝试往上跳就行了

#include <bits/stdc++.h>
using namespace std;
const int maxn=6e5+10;
int rt[maxn],sz[maxn],mx[maxn],fa[maxn],n,m;
struct p{int to,nxt;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v){d[cnt]=(p){v,head[u]},head[u]=cnt++;
}
void dfs(int now,int pre)
{sz[now]=1;for(int i=head[now];i;i=d[i].nxt){dfs( d[i].to,now );sz[now]+=sz[d[i].to];mx[now]=max(mx[now],sz[d[i].to]);}int me=mx[now];rt[now]=now;for(int i=head[now];i;i=d[i].nxt){int it=rt[ d[i].to ];int nice=max( mx[it],sz[now]-sz[it] ),k=it;while( fa[it]!=now ){it=fa[it];//往上跳int nn=max( mx[it],sz[now]-sz[it]);if( nn<nice )	nice=nn,k=it;else	break;//不会更优秀了 }if( me>nice ){me=nice;rt[now]=k;}}
}
int main()
{cin >> n >> m;for(int i=2;i<=n;i++){cin >> fa[i];add(fa[i],i);}dfs(1,0);while( m-- ){int x; cin >> x;cout << rt[x] << '\n';}return 0;
}