题目大意：给你一棵数q个询问，每个询问给你一个顶点编号，要你求以这个点为根的子树的重心是哪个节点。
定义：一棵树的顶点数为n，将重心去掉了以后所有子树的顶点的个数的两倍不会超过n。
性质 1 ：树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个距离和，他们的距离和一样。
性质 2 ：把两棵树通过某一点相连得到一颗新的树，新的树的重心必然在连接原来两棵树重心的路径上。
性质 3 ：一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。
1 #include<bits/stdc++.h> 2 #define fi first 3 #define se second 4 #define mk make_pair 5 #define ll long long 6 #define pll pair<ll,ll> 7 #define pii pair<int,int> 8 #define read(x) scanf("%d",&x) 9 #define sread(x) scanf("%s",x) 10 #define dread(x) scanf("%lf",&x) 11 #define lread(x) scanf("%lld",&x) 12 using namespace std; 13 14 15 const int N=1e6+7; 16 const int M=1e7+7; 17 const int inf=0x3f3f3f3f; 18 const ll INF=0x3f3f3f3f3f3f3f3f; 19 const int mod=1e9+7; 20 21 int n,q,sum[N],fa[N],ans[N]; 22 vector<int> edge[N]; 23 24 int dfs(int u) 25 { 26 sum[u]=1; ans[u]=u; 27 for(int v:edge[u]) 28 sum[u]+=dfs(v); 29 30 for(int v:edge[u]) 31 if(sum[v]*2>sum[u]) 32 ans[u]=ans[v]; 33 34 while((sum[u]-sum[ans[u]])*2>sum[u]) 35 ans[u]=fa[ans[u]]; 36 37 return sum[u]; 38 } 39 40 int main() 41 { 42 read(n); read(q); 43 for(int i=2;i<=n;i++) 44 { 45 int pre; read(pre); 46 edge[pre].push_back(i); 47 fa[i]=pre; 48 } 49 dfs(1); 50 while(q--) 51 { 52 int u; read(u); 53 printf("%d ",ans[u]); 54 } 55 return 0; 56 } 57 /* 58 59 */