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

1gnat2 · 2019-11-21 14:01:26 · 题解

根据重心的性质，这个题明显有O(n)解法。

以重心root为根。

记g_x表示子树x的重心，size(x)表示子树x的大小，mx_x表示x的子树大小最大的儿子。

那么g_x肯定在path(x,g_{mx_x})上。直接从g_{mx_x}向上走即可。总时间复杂度O(n)。

然后考虑去掉子树x的重心。去掉子树x后，重心root只可能向最大的儿子移动。

记root的次大儿子是mx'，第一步移动只可能向mx_{root}或mx'。

若x在子树mx_{root}内，且删去子树x后2size(mx')>n（此时2size(mx_{root})<n必然成立），则重心向mx'移动。

（显然，若root有多个次大儿子，则重心不可能向任一次大儿子移动。）

记g为当前重心，之后只可能向g_{mx}移动。

删除的子树越大重心移动得越远。各种线性复杂度的方法都行。

注意处理两个重心的情况。

总复杂度O(n)。

#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i,x,y) for (int i=x; i<=(y); ++i)
#define repe(i,x) for (edge *i=x; i; i=i->nxt)

int get()
{
    char c;
    while (!isdigit(c=getchar()));
    int k=c-'0';
    for (; isdigit(c=getchar()); k=k*10+c-'0');
    return k;
}

using namespace std;

typedef long long ll;

const int N=3e5;

int n,root,idx,id[N],s[N],mx[N],fa[N];
ll ans;

struct edge
{
    int v;
    edge *nxt;
} pool[N*2],*tp,*fst[N];

int dfs0(int x,int fa=0)
{
    s[x]=1;
    int v,mx=0;
    repe(i,fst[x])
        if ((v=i->v)!=fa)
        {
            int t=dfs0(v,x);
            if (t)
                return t;
            s[x]+=s[v],mx=max(mx,s[v]);
        }
    mx=max(mx,n-s[x]);
    return mx<<1<=n? x:0;
}

int dfs1(int x)
{
    id[x]=++idx,s[x]=1,mx[x]=0;
    int v,g=x;
    repe(i,fst[x])
        if ((v=i->v)!=fa[x])
        {
            fa[v]=x;
            int t=dfs1(v);
            s[x]+=s[v];
            if (s[v]>s[mx[x]])
                mx[x]=v,g=t;
        }
    if (x==root)
        return x;
    while (s[g]<<1<s[x])
        g=fa[g];
    ans+=s[g]<<1>s[x]? g:g+fa[g];
    return g;
}

int a[N],*pa;
int b[N],*pb;

int find(int &g,int n)
{
    while (s[mx[g]]<<1>=n)
        g=mx[g];
    return s[g]<<1>n? g:g+fa[g];
}

int gx[N],gy[N];

void work()
{
    tp=pool,memset(fst,0,sizeof(fst)),ans=0;
    n=get();
    rep(i,2,n)
    {
        int u=get(),v=get();
        *tp=(edge){v,fst[u]},fst[u]=tp++;
        *tp=(edge){u,fst[v]},fst[v]=tp++;
    }
    root=dfs0(1);
    idx=fa[root]=0,dfs1(root);

    int x=root,y=0;
    repe(i,fst[root])
        if (i->v!=mx[x] && s[i->v]>s[y])
            y=i->v;
    int mn=n-s[y]*2,l=id[mx[x]],r=l+s[mx[x]];
    rep(k,1,n-1)
        gx[k]=find(x,n-k);
    gx[n]=0;
    fill(gy+1,gy+mn,root);
    rep(k,mn,n-1)
        gy[k]=find(y,n-k);
    rep(i,1,n)
        ans+=l<=id[i] && id[i]<r? gy[s[i]]:gx[s[i]];
    printf("%lld\n",ans);
}

int main()
{
    for (int tc=get(); tc--; work());
    return 0;
}