题解 CF685B 【Kay and Snowflake】
Ryan_
2019-11-08 21:29:31
**题目描述:给出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;
}
}
```