题解 CF685B 【Kay and Snowflake】

发表于 | 更新于

$Description$

给出一棵树$($根是$1$$号节点 )$和$q$个询问,对于每个询问$v_i,$要求回答以$v_i$为根的子树的重心

$Solution$

先预处理出每个点$u$作为根时的答案，记为$ans[u],$最后$O(1)$回答。

记$u$的重儿子$($即$size$最大的儿子$)$为$son[u]$

考虑一个性质:如果以当前节点$u$为根$,size[son[u]]<=\frac{size[u]}{2},$所以$,ans[u]$只有可能是$u$自己或者在$son[u]$的子树中。

是$u$自己的情况根据$size[son[u]]$判断一下即可。

在$son[u]$的子树中的情况。因为$size[u]>size[son[u]],$所以$ans[u]$一定在$ans[son[u]]$的上方，因此我们只需要每次从以$son[u]$为根的子树的重心向上跳即可。

由于重心只会向上跳，所以跳的次数就是树高,所以总复杂度为$O(n)$

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define re register
#define N 405400
#define mod 1000000007
using namespace std;
struct edge{
    int to,next;
}e[N<<2];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int ans[N],fa[N],mx,loc,size[N],son[N],n,q,head[N],cnt=1;
inline void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u){
    size[u]=1;
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        dfs(v);
        size[u]+=size[v];
        if (size[v]>size[son[u]])son[u]=v;
    }
    if ((size[son[u]]<<1)>size[u]){
        int x=ans[son[u]];
        while (((size[u]-size[x])<<1)>size[u])x=fa[x];
        ans[u]=x;
    }else ans[u]=u;
}
signed main(){
    n=read(),q=read();
    for (int i=2;i<=n;++i)fa[i]=read(),add(fa[i],i);
    dfs(1);
    while (q--){
        int x=read();
        printf("%d\n",ans[x]);
    }
    return 0;
}