题目传送门

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=300500;
int read()
{
	int X=0; char ch=0;
	while(ch<48||ch>57) ch=getchar();
	while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
	return X;
}
vector<int>g[MAXN];
int siz[MAXN],p[MAXN],f[MAXN];
void pfs(int u)
{
	siz[u]=1;
	for(int i=0,v;i<g[u].size();i++)
	{
		if(!siz[v=g[u][i]])
		{
			f[v]=u;pfs(v);
			siz[u]+=siz[v];
		}
	}
	p[u]=0;
	for(int i=0,v;i<g[u].size();i++)
	{
		if((v=g[u][i])!=f[u]&&siz[v]>=siz[p[u]])
			p[u]=v;
	}
}
ll ans=0;
void upd(int &u,int c)
{
	while(siz[u]*2<c)u=f[u];
	while(siz[p[u]]*2>c)u=p[u];
	if(siz[p[u]]*2==c)ans+=p[u];
	if(siz[u]*2==c)ans+=f[u];

}
int n,u1,u2,c1,c2;
void dfs(int u,int fa)
{
	upd(u1,c1),upd(u2,c2);
	if(!p[u]) return ;
	f[f[fa]=u]=0;
	siz[u]+=siz[fa];
	int p1=0,p2=0,v,sp=p[u];
	for (int i=0;i<g[u].size();i++)
	{
    	v=g[u][i];
    	if (siz[v]>=siz[p1]){p2=p1;p1=v;}
    	else if (siz[v]>siz[p2])p2=v;
    }
    siz[u]-=siz[v=sp];
    if (p1==v)p[u]=p2;else p[u]=p1;
    c1=siz[u];c2=siz[v];
    if (u2==u)u2=v;
    dfs(v,u);
    siz[u]+=siz[v];
    int s1=u1,s2=u2;
    for (int i=0;i<g[u].size();i++)
      	if ((v=g[u][i])!=fa&&v!=sp)
		{
        	siz[u]-=siz[v];
			if (p1==v)p[u]=p2;else p[u]=p1;
			c1=siz[u];c2=siz[v];
			dfs(u2=v,u);
        	siz[u]+=siz[v];
      	}
	siz[u]-=siz[fa];
	f[f[u]=fa]=0;
	p[u]=sp;
}
void solve()
{
	n=read(),ans=0;
	for(int i=1;i<=n;i++) g[i].clear(),siz[i]=0;
	for (int i=1,f,t;i<n;i++)
	{
    	f=read();t=read();
    	g[f].push_back(t);
    	g[t].push_back(f);
  	}
	for (int i=1;i<=n;i++)
    	if (g[i].size()==1)
			u1=i;
	c1=1;c2=n-1;
	f[u2=g[u1][0]]=0;pfs(u2);
	siz[u2]--;
	if (p[u2]==u1)
		p[u2]=0;
	upd(u2,c2);ans=0;
	dfs(g[u1][0],u1);
	printf("%lld\n",ans);
}
int main()
{
	freopen("centroid.in","r",stdin);
    freopen("centroid.out","w",stdout);
	int T=read();
	while(T--)
		solve();
	return 0;
}