一定要好好看题啊......


引理:设$x,y$为一边上两点,若断去此边,不妨对于$x$所在子树,重心只会出现在重儿子链(包括$x$)上。

证明:根据重儿子的性质,其所属子树$size$是最大的,若不选重儿子$p_1$,而选轻儿子$p_2$,则有$\max\limits_{sub\in p_2}\ge \max\limits_{sub\in p_1}$,不利于$\max\limits_{sub\in p}\le \lfloor size/2\rfloor$,因此重心仅会出现在重儿子链上。

对于有可能出现两个重心的情况,重心一定是相邻的,因此也很好处理。

大体思路就是这样,注意根的转换。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define gc getchar()
#define ll long long
using namespace std;
const int N=3e5+10;
inline void qr(int &x)
{
    x=0;char c=gc;
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(ll x)
{
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct edge{int y,next;}a[N<<1];int len,last[N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
int son1[N],son2[N],son3[N],siz[N],p[N][18],c[N],fa[N],prf[N];
ll ans;
void dfs1(int x,int f)
{
    siz[x]=1;son1[x]=son2[x]=0;
    for(int k=last[x],y;k;k=a[k].next)
    {
        if(a[k].y==f)continue;
        dfs1(y=a[k].y,x);
        siz[x]+=siz[y];prf[y]=x;
        if(siz[son1[x]]<siz[y])son2[x]=son1[x],son1[x]=y;
        else if(siz[son2[x]]<siz[y])son2[x]=y;
    }
    p[x][0]=son1[x];
    for(int i=1;i<=17;i++)p[x][i]=p[p[x][i-1]][i-1];
}
inline int pd(int x,int sz){return x*(max(c[son3[x]],sz-c[x])<=(sz>>1));}
void dfs2(int x,int f)
{
    for(int k=last[x],y;k;k=a[k].next)
    {
        if(a[k].y==f)continue;
        y=a[k].y;
        c[x]=siz[1]-siz[y];fa[x]=fa[y]=0;//c[y]=siz[y];
        if(son1[x]==y)son3[x]=son2[x];
        else son3[x]=son1[x];
        if(c[f]>c[son3[x]])son3[x]=f;
        p[x][0]=son3[x];
        for(int i=1;i<=17;i++)p[x][i]=p[p[x][i-1]][i-1];
        int z=x;
        for(int i=17;~i;i--)if(c[x]-c[p[z][i]]<=(c[x]>>1))z=p[z][i];
        ans+=pd(son3[z],c[x])+pd(z,c[x])+pd(fa[z],c[x]);
        z=y;
        for(int i=17;~i;i--)if(c[y]-c[p[z][i]]<=(c[y]>>1))z=p[z][i];
        ans+=pd(son3[z],c[y])+pd(z,c[y])+pd(fa[z],c[y]);
        fa[x]=y;
        dfs2(y,x);
    }
    son3[x]=p[x][0]=son1[x];fa[x]=prf[x];
    for(int i=1;i<=17;i++)p[x][i]=p[p[x][i-1]][i-1];
    c[x]=siz[x];
}
int main()
{
    //freopen("a.in","r",stdin);
    int T;qr(T);
    while(T--)
    {
        memset(last,0,sizeof(last));len=0;memset(p,0,sizeof(p));
        memset(prf,0,sizeof(prf));
        int n;qr(n);
        for(int i=1,x,y;i<n;i++)qr(x),qr(y),ins(x,y),ins(y,x);
        dfs1(1,0);
        memcpy(fa,prf,sizeof prf);memcpy(son3,son1,sizeof son1);
        memcpy(c,siz,sizeof siz);
        ans=0;
        dfs2(1,0);
        qw(ans);puts("");
    }
    return 0;
}