题意:给定一棵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 }
01-10 20:23