题意：给定一棵n个点的树，q次询问，每次询问以某个点为根的子树编号是多少
n,q<=3e5
思路：设sz[u]为以u为根子树的size，v为u的size最大的儿子
若sz[v]*2<sz[u]则u即为重心
否则重心在以v为根的重心到u的路径上，暴力往上走，可以证明是均摊O(n)
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef unsigned int uint; 5 typedef unsigned long long ull; 6 typedef long double ld; 7 typedef pair<int,int> PII; 8 typedef pair<ll,ll> Pll; 9 typedef vector<int> VI; 10 typedef vector<PII> VII; 11 typedef pair<ll,ll>P; 12 #define N 500010 13 #define M 1000000 14 #define INF 1e9 15 #define fi first 16 #define se second 17 #define MP make_pair 18 #define pb push_back 19 #define pi acos(-1) 20 #define mem(a,b) memset(a,b,sizeof(a)) 21 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++) 22 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--) 23 #define lowbit(x) x&(-x) 24 #define Rand (rand()*(1<<16)+rand()) 25 #define id(x) ((x)<=B?(x):m-n/(x)+1) 26 #define ls p<<1 27 #define rs p<<1|1 28 #define fors(i) for(auto i:e[x]) if(i!=p) 29 30 const int MOD=1e9+7,inv2=(MOD+1)/2; 31 double eps=1e-6; 32 int dx[4]={-1,1,0,0}; 33 int dy[4]={0,0,-1,1}; 34 35 int head[N],vet[N],nxt[N],fa[N],sz[N],ans[N],f[N],tot; 36 37 int read() 38 { 39 int v=0,f=1; 40 char c=getchar(); 41 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 42 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 43 return v*f; 44 } 45 46 void add(int a,int b) 47 { 48 nxt[++tot]=head[a]; 49 vet[tot]=b; 50 head[a]=tot; 51 } 52 53 void dfs(int u) 54 { 55 int e=head[u]; 56 ans[u]=u; 57 sz[u]=1; 58 int mx=0,t=0; 59 while(e) 60 { 61 int v=vet[e]; 62 dfs(v); 63 sz[u]+=sz[v]; 64 if(sz[v]>mx) 65 { 66 mx=sz[v]; 67 t=v; 68 } 69 e=nxt[e]; 70 } 71 f[u]=mx; 72 if(f[u]*2<sz[u]) ans[u]=u; 73 else 74 { 75 int now=ans[t]; 76 while(fa[now]&&max(f[now],sz[u]-sz[now])>max(f[fa[now]],sz[u]-sz[fa[now]])) now=fa[now]; 77 ans[u]=now; 78 } 79 } 80 81 int main() 82 { 83 int n=read(),q=read(); 84 rep(i,1,n) head[i]=0; 85 tot=0; 86 rep(i,2,n) 87 { 88 fa[i]=read(); 89 add(fa[i],i); 90 } 91 dfs(1); 92 rep(i,1,q) 93 { 94 int x=read(); 95 printf("%d\n",ans[x]); 96 } 97 return 0; 98 }