Description
Link.
给定一棵 $n$ 个点的树，设 $E$ 为边集，$V'_x,\ V'_y$ 分别为删去边 $(x,y)$ 后 点 $x$ 所在的树的点集和点 $y$ 所在的树的点集，求：
$$ \sum_{(u,v)\in E}(\sum_{x\in V'_{u}}[x\text{ is the centroid of }V'_{u}]\times x+\sum_{y\in V'_{v}}[y\text{ is the centroid of }V'_{v}]\times y) $$
Solution
重心，想到重儿子，我们记一个结点 $u$ 的重儿子为 $hb_{u}$。
对于 $\text{subtree}(u)$，如果 $u$ 不是 $\text{subtree}(u)$ 的 centroid，那么 $\text{subtree}(u)$ 的 centroid 一定在 $\text{subtree}(hb(u))$ 里。
然后我们找到对于 $u$ 最深的一个重儿子 $v$（就是重链上的某个结点），满足 $siz_{u}-siz_{v}\le\frac{siz_{u}}{2}$，那么 $v$ 就是重心（还有 $fa_{v}$ 需要判断一下）。
对于这道题，我们直接枚举每条边 $(u,v)$，设 $u$ 比 $v$ 浅，那么 $v$ 就是 $V'_{v}$ 的根，直接套就可以了。
对于 $u$，我们换个根也就出来了，具体来说是交换 $(u,v)$ 的父子关系，不然直接交换 $(1,x)$ 太劣。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
vector<int> e[300010];
int t,n,siz[300010],hb[300010][20],fa[300010];
LL ans;
void dfs(int x,int las)
{
siz[x]=1,fa[x]=las;
for(unsigned int i=0;i<e[x].size();++i)
{
int y=e[x][i];
if(y^las)
{
dfs(y,x);
siz[x]+=siz[y];
if(siz[y]>siz[hb[x][0]]) hb[x][0]=y;
}
}
for(int i=1;i^20;++i) hb[x][i]=hb[hb[x][i-1]][i-1];
}
void cgfather(int x,int y)
{
siz[x]-=siz[y],siz[y]+=siz[x];
fa[x]=y,fa[y]=0;
if(hb[x][0]==y)
{
hb[x][0]=0;
for(unsigned int i=0;i<e[x].size();++i) if((e[x][i]^y)&&siz[e[x][i]]>siz[hb[x][0]]) hb[x][0]=e[x][i];
for(int i=1;i^20;++i) hb[x][i]=hb[hb[x][i-1]][i-1];
}
if(siz[x]>siz[hb[y][0]])
{
hb[y][0]=x;
for(int i=1;i^20;++i) hb[y][i]=hb[hb[y][i-1]][i-1];
}
}
void getans(int x)
{
#define eplist(x,all) (max(siz[hb[x][0]],(all)-siz[x])<=((all)>>1))
int now=x;
for(int i=19;~i;--i) if(hb[now][i]&&siz[x]-siz[hb[now][i]]<=(siz[x]>>1)) now=hb[now][i];
if(eplist(now,siz[x])) ans+=now;
if(eplist(fa[now],siz[x])) ans+=fa[now];
#undef eplist
}
void exdfs(int x,int las)
{
for(unsigned int i=0;i<e[x].size();++i)
{
int y=e[x][i];
if(y^las)
{
getans(y);
cgfather(x,y);
getans(x);
exdfs(y,x);
cgfather(y,x);
}
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1,x,y;i<n;++i)
{
scanf("%d %d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
dfs(1,0),exdfs(1,0);
printf("%lld\n",ans);
for(int i=1;i<=n;++i) e[i].clear(),siz[i]=hb[i][0]=fa[i]=0;
ans=0;
}
return 0;
}