补题……

看起来很憨憨。

但写起来未必好写。

反向枚举每个节点的贡献。

枚举是当前哪个子树上的删边。

这个显然可以 DSU on tree。

每个 BIT 维护当前子树删去各种边之后的 size。

要求支持平移、合并、区间求和。

区间求和是指，你要确定一个上界（其他节点数量）、一个下界（其余子树最大大小减其余点数目），求当前子树中有多少种删边方案使删完后仍合法。

但是以上都未考虑“父子树”的删边。

于是考虑换根 dp。

优先遍历重儿子。

直接计算其他子树带来贡献而维护成的 BIT。

然后遍历轻儿子。

每次在子树总贡献基础上去掉当前子树贡献，这个可以用类似淀粉质的容斥。

总复杂度 $O(n\log^2n)$。

常数比较小，根本不慌。

诶有多测。

那就不知道了。

草过去了。

#include<bits/stdc++.h>
#define o 300005
#define g0(a) memset(a,0,sizeof(a))
#define gc(a,b) memcpy(a,b,sizeof(a))
using namespace std;
inline int read()
{
	register int data=0,w=1;
	char ch=0;
	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
	if(ch=='-')w=-1,ch=getchar();
	while(ch>='0'&&ch<='9')data=(data<<1)+(data<<3)+(ch^48),ch=getchar();
	return data*w;
}
struct node
{
	int to,next;
}w[o*2];
int n,T,son[o],s[o],pr[o],son2[o],p[o][18],son3[o],f[o],h[o],cnt,s2[o];
void add(int x,int y){++cnt;w[cnt].to=y;w[cnt].next=h[x];h[x]=cnt;}
void dfs(int x,int fa)
{
	s[x]=1;pr[x]=fa;
	for(int i=h[x];i;i=w[i].next)
	{
		int y=w[i].to;
		if(y==fa)continue;
		dfs(y,x);s[x]+=s[y];
		if(s[y]>s[son[x]])son2[x]=son[x],son[x]=y;
		else if(s[y]>s[son2[x]])son2[x]=y;
	}
	p[x][0]=son[x];
	for(int i=1;i<=17;i++)p[x][i]=p[p[x][i-1]][i-1];
}
long long ans;
int judge(int x,int sum)
{
	return x*(max(s2[son3[x]],sum-s2[x])<=sum/2);
}
void dfs2(int x,int fa)
{
	for(int i=h[x];i;i=w[i].next)
	{
		int y=w[i].to;
		if(y==fa)continue;
		s2[x]=s[1]-s[y];f[y]=0;f[x]=0;
		if(son[x]==y)son3[x]=son2[x];
		else son3[x]=son[x];
		if(s2[fa]>s2[son3[x]])son3[x]=fa;
		p[x][0]=son3[x];
		for(int j=1;j<=17;j++)p[x][j]=p[p[x][j-1]][j-1];
		int b=x;
		for(int j=17;j>=0;j--)if(s2[x]-s2[p[b][j]]<=s2[x]/2)b=p[b][j];
		ans+=judge(son3[b],s2[x])+judge(b,s2[x])+judge(f[b],s2[x]);
		b=y;
		for(int j=17;j>=0;j--)if(s2[y]-s2[p[b][j]]<=s2[y]/2)b=p[b][j];
		ans+=judge(son3[b],s2[y])+judge(b,s2[y])+judge(f[b],s2[y]);
		f[x]=y;
		dfs2(y,x);
	}
	son3[x]=p[x][0]=son[x];f[x]=pr[x];
	for(int j=1;j<=17;j++)p[x][j]=p[p[x][j-1]][j-1];
	s2[x]=s[x];
}
int main()
{
	T=read();
	while(T--)
	{
		g0(h);g0(son);g0(f);g0(pr);cnt=0;ans=0;
		n=read();
		for(int i=1;i<n;i++)
		{
			int x=read(),y=read();
			add(x,y);add(y,x);
		}
		dfs(1,0);
		gc(s2,s);gc(son3,son);gc(f,pr);
		dfs2(1,0);
		cout<<ans<<'\n';
	}
	return 0;
}