#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans,flag[100010],ku,kv,kw,t;
int js(int n)
{
	return ((n+1)*n)/2;
}
signed main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<n;i++)
		scanf("%d%d",&ku,&kv);
		if(n%2==1)
		ans=3*js(n)-(n+1)/2-n-1;;
		if(n%2==0)
		ans=3*js(n)-n/2-n/2-1-n-1;
		printf("%lld\n",ans);
	}
	return 0;
}

如果是链的情况，我推出来当n%2==1时1结点和n结点以及最中间结点就是（n+1）/2结点只被算了两次，其余结点算了三次。  
 

当n%2==0时1结点和n结点以及中间两个结点就是n/2结点和n/2+1号结点只被算了两次，其余结点算了三次。