题解 P5666 【树的重心【民间数据】】

本题解远短于其他题解,只需要两次dfs和一次倍增

二叉树:

深度较浅,暴力换重儿子

对于一个点,若x不是重心,重心要么在重儿子子树里,要么在父亲节点上

第一次dfs求出son[x],s[x]

p[x][i]表示x沿着重儿子走2^i步

第二次dfs换根,把上面数组的定义从以1为根改为以x为根

对于一条边,以下方的重心,可以直接倍增,可以跳的条件为上方

的size<=sum/2

对于上方的重心,换根时记录信息,倍增方法一样

于是我们就用纯CSP算法解决了CSP2019 Day2 T3

给出简短的代码

#include<bits/stdc++.h>
#define o 300005
#define g0(a) memset(a,0,sizeof(a))
#define gc(a,b) memcpy(a,b,sizeof(a))
using namespace std;
inline int read()
{
    register int data=0,w=1;
    char ch=0;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')data=(data<<1)+(data<<3)+(ch^48),ch=getchar();
    return data*w;
}
struct node
{
    int to,next;
}w[o*2];
int n,T,son[o],s[o],pr[o],son2[o],p[o][18],son3[o],f[o],h[o],cnt,s2[o];
void add(int x,int y){++cnt;w[cnt].to=y;w[cnt].next=h[x];h[x]=cnt;}
void dfs(int x,int fa)
{
    s[x]=1;pr[x]=fa;
    for(int i=h[x];i;i=w[i].next)
    {
        int y=w[i].to;
        if(y==fa)continue;
        dfs(y,x);s[x]+=s[y];
        if(s[y]>s[son[x]])son2[x]=son[x],son[x]=y;
        else if(s[y]>s[son2[x]])son2[x]=y;
    }
    p[x][0]=son[x];
    for(int i=1;i<=17;i++)p[x][i]=p[p[x][i-1]][i-1];
}
long long ans;
int judge(int x,int sum)
{
    return x*(max(s2[son3[x]],sum-s2[x])<=sum/2);
}
void dfs2(int x,int fa)
{
    for(int i=h[x];i;i=w[i].next)
    {
        int y=w[i].to;
        if(y==fa)continue;
        s2[x]=s[1]-s[y];f[y]=0;f[x]=0;
        if(son[x]==y)son3[x]=son2[x];
        else son3[x]=son[x];
        if(s2[fa]>s2[son3[x]])son3[x]=fa;
        p[x][0]=son3[x];
        for(int j=1;j<=17;j++)p[x][j]=p[p[x][j-1]][j-1];
        int b=x;
        for(int j=17;j>=0;j--)if(s2[x]-s2[p[b][j]]<=s2[x]/2)b=p[b][j];
        ans+=judge(son3[b],s2[x])+judge(b,s2[x])+judge(f[b],s2[x]);
        b=y;
        for(int j=17;j>=0;j--)if(s2[y]-s2[p[b][j]]<=s2[y]/2)b=p[b][j];
        ans+=judge(son3[b],s2[y])+judge(b,s2[y])+judge(f[b],s2[y]);
        f[x]=y;
        dfs2(y,x);
    }
    son3[x]=p[x][0]=son[x];f[x]=pr[x];
    for(int j=1;j<=17;j++)p[x][j]=p[p[x][j-1]][j-1];
    s2[x]=s[x];
}
int main()
{
    T=read();
    while(T--)
    {
        g0(h);g0(son);g0(f);g0(pr);cnt=0;ans=0;
        n=read();
        for(int i=1;i<n;i++)
        {
            int x=read(),y=read();
            add(x,y);add(y,x);
        }
        dfs(1,0);
        gc(s2,s);gc(son3,son);gc(f,pr);
        dfs2(1,0);
        cout<<ans<<'\n';
    }
    return 0;
}