P5666 树的重心解题报告&关于树的重心的奇技淫巧

解题报告 杂项

虽然这道题已经写不了解题报告了，但是还是写一下题解纪念我一个下午+一个上午的努力吧。

P5666 树的重心

题意

• 给定一棵$n$个点的树，求割断每一条边后两棵树的重心的编号和。
• 数据范围：$1\leqslant n\leqslant3\times 10^5$。

分析

树上毒瘤题。

为了方便，我们设重心为根节点。

首先，给定一些关于树的重心的性质：

• 树的重心所有儿子子树大小的最大值不超过这棵树的大小的一半。
• 树的重心数量一定为$1$和$2$，且如果树有两个重心，那么它们一定相邻。
• 树的重心一定在根节点的重链上。
• 树的重心一定在它重儿子的重心到根节点的路径上。

我们发现割断每一条边求两棵树的重心等价于求一棵子树的重心和整棵树去掉一棵子树的重心，那么下面进行分类讨论：

（注意，根据性质$2$，我们可以找到深度较深的重心，然后判断它的父亲是否也为重心）

求一棵子树的重心

根据上面的性质$4$，我们可以$O(n)$求出所有子树的重心。

具体的说，我们直接找到重儿子的重心，然后暴力向上跳直到这个点满足重心的定义。

简单说明一下复杂度为什么是正确的：很显然每一条边最多被一次暴力跳经过，因此复杂度为$O(n)$。

void dfs2(int x,int last){
    if(iptson[x]==-1){//是叶子节点
        treepos[x]=x;
        return ;
    }
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs2(y,x);
    }
    int now=treepos[iptson[x]];
    while(size[x]-size[now]>size[x]/2)
        now=fa[now];
    treepos[x]=now;
}

求整棵树去掉一棵子树的重心

这个非常麻烦，我们需要继续分类讨论：

这颗子树不在根节点重儿子的子树中

因为这样的操作后重儿子仍然是重儿子，因此重心只会在根节点所在的重链上。进而有一个结论：只要删去的子树的大小相同，重心位置就相同。这样，我们就可以暴力预处理出来删除每个大小的子树的重心位置。

这棵子树在根节点重儿子的子树中

如果删除了这棵子树后重儿子仍然是重儿子，那么重心就是根节点（这个很显然，因为根节点是原来的重心）。

否则我们可以像上面一样进行预处理。

int dfs3(int x,int p){//p=0表示预处理根节点重儿子，p=1表示预处理跟节点次重儿子
    int now;
    if(iptson[x]==-1)
        now=n-(p==0? size[iptson[pos]]:size[secson[pos]]);//删的再多也不能删到（次）重儿子所在的子树上
    else{
        if(x==pos&&p==1)
            now=dfs3(secson[x],1);
        else now=dfs3(iptson[x],p);
    }
    while(now>0&&n-now-size[x]<=(n-now)/2)
        except[now][p]=x,now--;
    return now;
}

因为上面的$\text{while}$循环只需要执行$now$次，而$now$是$O(n)$的，因此这种预处理也是$O(n)$的。

然后是求答案的部分：

（注意，$flg_x$为$x$是否在根节点重儿子子树中，$1$代表在）

int solve(){
    int res=0;
    for(int i=1;i<n;i++){
        int x=xx[i],y=yy[i];
        if(dep[x]>dep[y])//保证$y$是$x$的儿子
            swp(x,y);
        int c1=treepos[y],c2=fa[c1],c3=0,c4=0;//c1,c2,c3,c4为四个重心位置（c1,c2在y子树里，c3,c4在y子树外）
        if(c2==0||size[iptson[c2]]>size[y]/2)//如果不存在c2或者c2的重儿子大小大于总大小的1/2,那么y子树中没有第二个重心
            c2=0;
        //下面讨论不在y子树中的重心
        if(flg[y]==0){//不在根节点重儿子所在的子树中
            c3=except[size[y]][0],c4=fa[c3];
            if(c4==0||size[iptson[c4]]>(n-size[y])/2)//如果不存在出或者c4的重儿子大小大于总大小的1/2,那么y子树外没有第二个重心
                c4=0;
        }
        if(flg[y]==1){//在根节点重儿子所在的子树中
            if(size[iptson[pos]]-size[y]>=size[secson[pos]])//不破坏重儿子，那么重心就是根节点
                c3=pos,c4=0;
            else{//破坏重儿子
                c3=except[size[y]][1],c4=fa[c3];
                int c4son=c4==pos? secson[c4]:iptson[c4];
                if(c4==0||size[c4son]>(n-size[y])/2)//如果不存在c4或者c4的某个儿子大小大于总大小的1/2，那么y子树外没有第二个重心（注意这里如果c4为根节点，那么因为重儿子大小小于次重儿子，所以需要取次重儿子大小）
                    c4=0;
            }
        }
        res+=c1+c2+c3+c4;
    }
    return res;
}

综上所述，总时间复杂度：$O(n)$。

代码

#include<stdio.h>
#include<string.h>
#define int long long
#define inf 100000000000000000
const int maxn=300005,maxm=600005;
int T,n,e,minn,pos;
int start[maxn],to[maxm],then[maxm],size[maxn],iptson[maxn],secson[maxn],flg[maxn],dep[maxn],treepos[maxn],fa[maxn],except[maxn][2],xx[maxn],yy[maxn];
inline int max(int a,int b){
    return a>b? a:b;
}
inline void swp(int &a,int &b){
    a+=b,b=a-b,a-=b;
}
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
int getcenter(int x,int last){//找重心
    int sz=1,maxx=0;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        int res=getcenter(y,x);
        sz+=res,maxx=max(maxx,res);
    }
    maxx=max(maxx,n-sz);
    if(maxx<minn)
        minn=maxx,pos=x;
    return sz;
}
void dfs1(int x,int last){//预处理各种变量
    iptson[x]=secson[x]=-1,size[x]=1,dep[x]=dep[last]+1,fa[x]=last;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs1(y,x);
        size[x]+=size[y];
        if(iptson[x]==-1||size[y]>size[iptson[x]])
            secson[x]=iptson[x],iptson[x]=y;
        else if(secson[x]==-1||size[y]>size[secson[x]])
            secson[x]=y;
    }
}
void dfs2(int x,int last){//求子树重心
    flg[x]=flg[last];
    if(x==iptson[pos])
        flg[x]=1;
    if(iptson[x]==-1){
        treepos[x]=x;
        return ;
    }
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs2(y,x);
    }
    int now=treepos[iptson[x]];
    while(size[x]-size[now]>size[x]/2)
        now=fa[now];
    treepos[x]=now;
}
int dfs3(int x,int p){//求删除某个大小的子树后重心的位置
    int now;
    if(iptson[x]==-1)
        now=n-(p==0? size[iptson[pos]]:size[secson[pos]]);
    else{
        if(x==pos&&p==1)
            now=dfs3(secson[x],1);
        else now=dfs3(iptson[x],p);
    }
    while(now>0&&n-now-size[x]<=(n-now)/2)
        except[now][p]=x,now--;
    return now;
}
int solve(){//求解答案
    int res=0;
    for(int i=1;i<n;i++){
        int x=xx[i],y=yy[i];
        if(dep[x]>dep[y])
            swp(x,y);
        int c1=treepos[y],c2=fa[c1],c3=0,c4=0;
        if(c2==0||size[iptson[c2]]>size[y]/2)
            c2=0;
        if(flg[y]==0){
            c3=except[size[y]][0],c4=fa[c3];
            if(c4==0||size[iptson[c4]]>(n-size[y])/2)
                c4=0;
        }
        if(flg[y]==1){
            if(size[iptson[pos]]-size[y]>=size[secson[pos]])
                c3=pos,c4=0;
            else{
                c3=except[size[y]][1],c4=fa[c3];
                int c4son=c4==pos? secson[c4]:iptson[c4];
                if(c4==0||size[c4son]>(n-size[y])/2)
                    c4=0;
            }
        }
        res+=c1+c2+c3+c4;
    }
    return res;
}
signed main(){
    scanf("%lld",&T);
    while(T--){
        e=0;
        memset(start,0,sizeof(start));
        memset(except,0,sizeof(except));
        memset(fa,0,sizeof(fa));
        memset(flg,0,sizeof(flg));
        scanf("%lld",&n);
        for(int i=1;i<n;i++){
            int x,y;
            scanf("%lld%lld",&x,&y);
            xx[i]=x,yy[i]=y;
            add(x,y),add(y,x);
        }
        minn=inf,pos=0;
        getcenter(1,0);
        dfs1(pos,0);
        dfs2(pos,0);
        dfs3(pos,0);
        dfs3(pos,1);
        printf("%lld\n",solve());
    }
    return 0;
}