题解： CF685B Kay and Snowflake

· · 题解

前置芝士：重链剖分。

这里来一个个人认为很好理解的新做法。

重心有一个比较典的性质是：一棵树的重心是根节点所在重链上，深度最大的满足 sz_u \times 2>sz_{root} 的点（sz 是子树大小，u 是当前点，root 是这棵树的根）。

知道了这个性质之后我们考虑剖出重链然后如何快速求出这个深度最大的 u。一个比较自然的思路是在重链上向下二分，直接在树上二分显然是不行的，但是发现重链上的点拍到 dfn 序列上是连续的，那么就支持我们在 dfn 序列上二分了。

每次二分的右界需要单独处理一下，在预处理的时候求出每个点所在重链向下的长度还有多少。

时间复杂度 O(n+q \log n)，虽然理论上比 O(n) 的慢一些但是可能因为常数问题，它的速度遥遥领先于大部分 O(n) 的解法。

笔者认为在重链上二分的思路可能不需要动脑子，且在更强问题上更有前途。

AC code：

#include<bits/stdc++.h>
using namespace std;
const int N=300010;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,q,fa[N],len[N],sz[N],son[N],dfn[N],rnk[N],cnt;
vector<int> e[N];
void dfs1(int now){
    sz[now]=1;
    for(int i=0;i<(int)e[now].size();i++){
        int to=e[now][i];
        dfs1(to);
        sz[now]+=sz[to];
        if(sz[to]>sz[son[now]])son[now]=to;
    }
}
void dfs2(int now){
    dfn[now]=++cnt,rnk[cnt]=now;
    if(son[now]==0){
        len[now]=1;
        return;
    }
    dfs2(son[now]);
    len[now]=len[son[now]]+1;
    for(int i=0;i<(int)e[now].size();i++){
        int to=e[now][i];
        if(son[now]==to)continue;
        dfs2(to);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    n=read(),q=read();
    for(int i=2;i<=n;i++)fa[i]=read(),e[fa[i]].push_back(i);
    dfs1(1);dfs2(1);
    for(int i=1;i<=q;i++){
        int a=read();
        int l=dfn[a],r=dfn[a]+len[a]-1,ans=l;
        while(l<=r){
            int mid=(l+r)>>1;
            if(2*sz[rnk[mid]]>sz[a])l=mid+1,ans=mid;
            else r=mid-1;
        }
        cout<<rnk[ans]<<'\n';
    }
    return 0;
}