CF685B Kay and Snowflake

· · 题解

本蒟蒻的第一篇题解

这是一道树的重心，不知道的建议先去做做模板题 P1395 会议

很容易想到的做法就是暴力地直接对每个询问进行的 dfs,找到这棵子树得重心 ， 但是显而易见会超时，考虑预先求出每棵子树的重心，查询时 O（1）输出该子树重心，这道题就可以 AC 了。

那么如何求每棵子树的重心呢 ？

对于一颗树它的重心在初始根节点或者最重子树上

依据树的重心的性质，所有点到重心的距离和最小。换言之以重心为根时，所有点的深度和最小。若把根节点定在任意节点时，则该节点的所有子节点深度都减小，相应的其他子树的节点的深度会增加。最大子树子节点最多，所以深度和减小就最多，所以把根节点放在最大子树上会优于放在其他子树上，所以一棵树的重心不在初始根节点上就在初始根节点的最大子树上。

把两棵树通过一条边相连，新的树的重心在原来两颗树重心的连线上

在搜索一颗子树时可以看做把这颗子树和之前的节点与根节点形成的数之间通过一条边相连

由此可得一颗树的重心在这颗树的最重子树的重心与根节点的连线上。

所以对于每一个根节点，我们找到它的最重子树从最重子树的重心往上跳，从而找到这个根节点下的子树的重心。

往上跳时还有一个结论，如果此时结果不如上一个节点更优，则继续跳下去也不会更优。因为此时深度增加的点的个数已经多于深度减小的点的个数，再跳下去这个差值会更大，故不可能更优。

优劣判断用输的重心的性质：以树的重心为根时，所有子树的大小都不超过整棵树大小的一半

下面是我的 AC 代码

#include <bits/stdc++.h>
using namespace std;
const int N=6e5+9,MAX=0x3f3f3f3f;
int n,q,cnt,fa[N],ans[N],pre[N],last[N],other[N],size[N];
void add(int x,int y)
{
    pre[++cnt]=last[x];
    last[x]=cnt;
    other[cnt]=y;
}
void dfs(int x)
{
    int maxs=0;//初始化最大子树的大小为0 
    int an=0;//用于记录最大子树所在的子节点 
    ans[x]=x;//初始化每棵子树的重心为这棵子树的初始根 
    size[x]=1;
    for(int i=last[x];i;i=pre[i])
    {
        int y=other[i];
        dfs(y);
        size[x]+=size[y];//计算子树大小 
        if(size[y]>maxs) //比较最大子树并记录 
        {
            maxs=size[y];
            an=y;
        }
    }
    if(2*size[an]>size[x])//以树的重心为根时，所有子树的大小都不超过整棵树大小的一半
    {
        int temp=ans[an];
        while(2*(size[x]-size[temp])>size[x])
        {
            temp=fa[temp];
        }
        ans[x]=temp;
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=2;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        fa[i]=x;
        add(x,i);
    }
    dfs(1);
    for(int i=1;i<=q;i++)
    {
        int x;
        scanf("%d",&x);
//      cout<<"ans: ";
        cout<<ans[x]<<endl;
    }
}