【题解】「CSP 2019」树的重心 Loj3213

考虑一个节点 $u$ 的贡献。

将这个节点 $u$ 作为根，考虑其儿子集合 ${v_1,v_2,\cdots, v_n}$ ，一种合法的删边方式必须满足，删完这条边后 $\max siz(v_i)\leq \lfloor\frac{\sum siz(v_i)+1}{2}\rfloor$ 。删除的边一定是某个节点 $x\not =u$ 到其父亲的边，如果 $x$ 属于 $v_i$ 的子树，那么删除该边的意义就是将 $siz(v_i)$ 减去 $siz(x)$ 。

设删去的这条边属于 $v_i$ 的子树，那么一定要满足：

• $\max_{j\not =i} siz(v_j)\leq \lfloor\frac{n-siz(x)}{2}\rfloor$ ，即：$siz(x)\leq n-2\left(\max_{j\not =i} siz(v_j)\right)$
• $siz(v_i)-siz(x)\leq \lfloor\frac{n-siz(x)}{2}\rfloor$ ，即：$2siz(v_i)-n\leq siz(x)$

也就是说，对于满足 $2siz(v_i)-n\leq siz(x)\leq n-2\left(\max_{j\not =i} siz(v_j)\right)$ 的 $x\not =u$ ，删去 $x$ 到其父亲的边后 $u$ 可以作为重心。要想知道 $u$ 做了几次贡献就只需要找到合法范围内的 $x$ 个数即可。

实际操作的时候不可能将 $u$ 作为根来操作，这时将子树分成两类。若是 $u$ 的内子树，直接用线段树合并处理。若是 $u$ 的外子树，直接维护不可取，不妨干脆维护所有的节点，然后再减去就是了，这样子的话每一次移动节点只需要在维护外子树的线段树上进行一次修改。

时间复杂度 $O(n\log n)$ 。

const int N=3e5+5;
int n,siz[N]; ll ans;
std::vector <int> son[N];

// {{{ Segment_Tree

#define mid ((l+r)>>1)

const int M=2e7+5;
int tot,rt[N],lc[M],rc[M],sum[M];

void insert(int &x,int l,int r,int pos) {
    if(!x) x=++tot; ++sum[x];
    if(l==r) return ;
    pos<=mid?insert(lc[x],l,mid,pos):insert(rc[x],mid+1,r,pos);
}
int query(int x,int l,int r,int L,int R) {
    if(L>R) return 0;
    if(L==l&&r==R) return sum[x];
    if(R<=mid) return query(lc[x],l,mid,L,R);
    if(L>mid) return query(rc[x],mid+1,r,L,R);
    return query(lc[x],l,mid,L,mid)+query(rc[x],mid+1,r,mid+1,R);
}

int merge(int x,int y) {
    if(!x||!y) return x|y;
    int z=++tot; sum[z]=sum[x]+sum[y];
    lc[z]=merge(lc[x],lc[y]),rc[z]=merge(rc[x],rc[y]);
    return z;
}

// }}}

// {{{ BIT

int c[N],res;
inline int lowbit(int x) {return x&(-x);}
inline void modify(int x,int y) {for(;x<=n;x+=lowbit(x)) c[x]+=y;}
inline int query(int x) {
    if(x<1) return 0;
    res=0; for(;x;x-=lowbit(x)) res+=c[x]; return res;
}

// }}}

void init(int u,int fa) {
    siz[u]=1;
    for(int v:son[u]) if(v!=fa) init(v,u),siz[u]+=siz[v];
    insert(rt[u],1,n,siz[u]),modify(siz[u],1);
    for(int v:son[u]) if(v!=fa) rt[u]=merge(rt[u],rt[v]);
}

int sta[N],pre[N],suf[N];
void solve(int u,int fa) {
    int sum=0,tmp=0,top=0;
    for(int v:son[u]) if(v!=fa) sta[++top]=v;

    pre[0]=suf[top+1]=0;
    lep(i,1,top) pre[i]=max(pre[i-1],siz[sta[i]]);
    rep(i,top,1) suf[i]=max(suf[i+1],siz[sta[i]]);

    lep(i,1,top) { 
        int res=max(n-siz[u],max(pre[i-1],suf[i+1]));
        sum+=query(rt[sta[i]],1,n,max(1,2*siz[sta[i]]-n),max(0,n-2*res));
    }

    sum+=query(max(0,n-2*pre[top]))-query(max(1,2*(n-siz[u])-n)-1);
    sum-=query(rt[u],1,n,max(1,2*(n-siz[u])-n),max(0,n-2*pre[top]));
    ans+=1ll*u*sum;

    modify(siz[u],-1);
    for(int v:son[u]) if(v!=fa)
        modify(n-siz[v],1),solve(v,u),modify(n-siz[v],-1);
    modify(siz[u],1);
}

inline void solve() {
    IN(n); int u,v;
    lep(i,0,n) son[i].clear();
    lep(i,2,n) IN(u,v),son[u].pb(v),son[v].pb(u);

    lep(i,0,tot) lc[i]=rc[i]=sum[i]=0; tot=0;
    lep(i,0,n) c[i]=0,rt[i]=0;

    ans=0,init(1,0),solve(1,0);
    printf("%lld\n",ans);
}

int main() {
    int T=int(IN);
    while(T--) solve();
    return 0;
}