§ Description

Link.

给定一棵 $n$ 个点的树，设 $E$ 为边集，$V'_x,\ V'_y$ 分别为删去边 $(x,y)$ 后 点 $x$ 所在的树的点集和点 $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;
}