不是吧不是吧，这种真题居然还轮得到我这种一年之后的老年选手写题解（

更好的阅读体验

Statement

给定一棵 $n$ 点的树，求单独删去每条边之后，分裂出的两个子树的重心编号和之和。（重心定义和简单性质自行阅读题面）

$n\leq 299995$ .

Thoughts & Solution

55pts 有手就行

考场骗分小能手狂喜（

发现前面 40 分的部分分完全可以 $\mathcal{O}(n^2)$ 暴力碾过去，枚举删边，然后 $\mathcal{O}(n)$ DFS求一遍重心即可。

对于后面 15 分，有性质 $A$ 也就是链。对于链，重心显然是找个中点就好了。

75pts 完全二叉树

咳……这个要面向数据。

注意到题目里面对于这个部分分，钦定了 $n=262143$ ，算一算就会发现是个满二叉树……其实满二叉树的根节点就是重心……

那么可以得到如下推论：

• 对于删掉的某一条边，儿子节点就是它这个子树的重心
• 对于根节点，如果在左子树里面删了一条边，那么右儿子就是剩余部分的重心
• 对于叶子节点，删掉之后根就是剩余部分的重心

然后直接 $\mathcal{O}(n)$ 枚举 $\mathcal{O}(1)$ 计算就好了。

正解

考虑重心的出现位置。有结论：

对于一个节点 $u$ ，如果 $n-siz[u]\leq \lfloor n/2\rfloor$ ，且 $u$ 本身并非重心，那么重心一定在 $u$ 的重儿子里面。

这个挺显然的的吧。

然后就有一些显然的推论：（此处的 $u$ 依然满足 $n-siz[u]\leq\lfloor n/2\rfloor$ ）

• 前置：显然 $u$ 只有一个重儿子。
• 重心的可能位置只有两种，要么是 $u$ 要么在 $u$ 的重子树里面。
• 如果 $u$ 是满足这个条件且 $dep[u]$ 最大的点，那么根据上面的结论， $u$ 就是重心，且 $fa[u]$ 也有可能是重心。

因此，重心一定在 root 向下的重链上，而且重链上自上往下，节点的 $siz$ 递减。再结合数据范围得到合理猜测：复杂度 $\mathcal{O}(n\log n)$ .

那么就可以考虑在重链上倍增。令 $f[i][x]$ 表示以 rt 为根，节点 $x$ 沿着重链往下走 $2^i$ 步达到的节点。这样，求重心的时候就类似 LCA 一样，逆序枚举 $i$ 往下跳就好了。

然后类似换根DP，二次扫描维护 $f$ 数组和重儿子即可。

时间复杂度是 $\mathcal{O}(n\log n)$ .

//Author: RingweEH
const int N=3e5+10,K=25;
struct edge
{
    int to,nxt;
}e[N<<1];
int head[N],tot=0,n,siz[N],f[N][K],son[N],fa[N];
ll ans;

void ST_init( int x )
{
    for ( int i=1; i<K; i++ )
        f[x][i]=f[f[x][i-1]][i-1];
}

void calc( int x )
{
    int u=x;
    for ( int i=K-2; i>=0; i-- )
        if ( f[u][i] && siz[f[u][i]]*2>=siz[x] ) u=f[u][i];
    if ( siz[u]*2==siz[x] ) ans+=fa[u];
    ans+=u;
}

void dfs( int u,int fat )
{
    fa[u]=fat; siz[u]=1; siz[0]=0; son[u]=0;
    for ( int i=head[u]; i; i=e[i].nxt )
    {
        int v=e[i].to;
        if ( v==fat ) continue;
        dfs( v,u ); siz[u]+=siz[v];
        if ( siz[v]>siz[son[u]] ) son[u]=v; //重儿子
    }
    f[u][0]=son[u]; ST_init( u );
}

void get_ans( int u,int fat )
{
    int mx1=0,mx2=0; siz[0]=0;
    for ( int i=head[u]; i; i=e[i].nxt )
    {
        int v=e[i].to;
        if ( siz[v]>=siz[mx1] ) mx2=mx1,mx1=v;
        else if ( siz[v]>=siz[mx2] ) mx2=v;
        //最大和次大的儿子
    }
    for ( int i=head[u]; i; i=e[i].nxt )
    {
        int v=e[i].to;
        if ( v==fat ) continue;
        calc( v ); f[u][0]=(v==mx1) ? mx2 : mx1; ST_init( u );
        siz[u]-=siz[v]; siz[v]+=siz[u];
        calc( u ); fa[u]=v; get_ans( v,u );
        siz[v]-=siz[u]; siz[u]+=siz[v];     //算完(u,v)之后撤销影响
    }
    f[u][0]=son[u]; ST_init( u ); fa[u]=fat;
}

void add( int u,int v )
{
    e[++tot].to=v; e[tot].nxt=head[u]; head[u]=tot;
    e[++tot].to=u; e[tot].nxt=head[v]; head[v]=tot;
}

int main()
{
//freopen( "centroid.in","r",stdin ); freopen( "centroid.out","w",stdout );

    int T=read();
    while ( T-- )
    {
        memset( siz,0,sizeof(siz) ); memset( son,0,sizeof(son) );
        memset( f,0,sizeof(f) ); memset( fa,0,sizeof(fa) ); ans=0;
        memset( head,0,sizeof(head) ); tot=0;

        n=read();
        for ( int i=1,u,v; i<n; i++ )
            u=read(),v=read(),add( u,v );

        dfs( 1,0 ); get_ans( 1,0 );

        printf( "%lld\n",ans );
    }

//fclose( stdin ); fclose( stdout );
    return 0;
}