代码虽然比较长，但是可读性不低，求调

#include<bits/stdc++.h>
using namespace std;

int num;
char ch;
int read()
{
	num=0;
	ch=getchar();
	while(ch<'0'||ch>'9')
	{
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		num=(num<<1)+(num<<3)+ch-'0';
		ch=getchar();
	}
	return num;
}

int n,head[299996];
struct edge{
	int to,next;
}e[599991];
int mx,submx;
int size[299996],max_subtree[299996],weight[299996],centroid,root;
struct segment_tree{
	int l,r,sum;
}t[1199981];
int ans[299996];

void build(int p,int l,int r)//of segment tree
{
	t[p].l=l;
	t[p].r=r;
	t[p].sum=0;
	if(l==r)
	{
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}

void change(int p,int index,int add)//of segment tree
{
	if(t[p].l>index||t[p].r<index)
	{
		return;
	}
	if(t[p].l==index&&t[p].r==index)
	{
		t[p].sum+=add;
		return;
	}
	change(p<<1,index,add);
	change(p<<1|1,index,add);
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}

int ask(int p,int l,int r)//of segment tree
{
	if(t[p].l>r||t[p].r<l)
	{
		return 0;
	}
	if(t[p].l>=l&&t[p].r<=r)
	{
		return t[p].sum;
	}
	return ask(p<<1,l,r)+ask(p<<1|1,l,r);
}

void add_edge(int from,int to,int id)
{
	e[id]=edge{to,head[from]};
	head[from]=id;
}

void find_centroid(int now,int father)
{
	size[now]=1;
	weight[now]=0;
	for(int i=head[now];i;i=e[i].next)
	{
		if(e[i].to==father)
		{
			continue;
		}
		find_centroid(e[i].to,now);
		size[now]+=size[e[i].to];
		weight[now]=max(weight[now],size[e[i].to]);
	}
	weight[now]=max(weight[now],n-size[now]);
	if(weight[now]<=(n>>1))
	{
		centroid=now;
	}
}

void calc_size(int now,int father)
{
	size[now]=1;
	max_subtree[now]=0;
	for(int i=head[now];i;i=e[i].next)
	{
		if(e[i].to==father)
		{
			continue;
		}
		calc_size(e[i].to,now);
		size[now]+=size[e[i].to];
		max_subtree[now]=max(max_subtree[now],size[e[i].to]);
	}
}

void calc_root()//find mx and submx
{
	mx=submx=0;
	for(int i=head[root];i;i=e[i].next)
	{
		if(size[e[i].to]>size[mx])
		{
			mx=e[i].to;
		}
	}
	for(int i=head[root];i;i=e[i].next)
	{
		if(size[e[i].to]>size[submx]&&e[i].to!=mx)
		{
			submx=e[i].to;
		}
	}
}

void calc_neg(int now,int father)//negative contribution
{
	change(1,size[now],1);
	change(1,n-size[now],1);
	if(now==root)
	{
		ans[now]=0;
		calc_root();
		for(int i=head[root];i;i=e[i].next)
		{
			if(e[i].to==mx)
			{
				ans[now]+=ask(1,0,n-(size[mx]<<1));
				ans[now]-=ask(1,0,n-(size[submx]<<1));
				calc_neg(mx,root);
				ans[now]-=ask(1,0,n-(size[mx]<<1));
				ans[now]+=ask(1,0,n-(size[submx]<<1));
				continue;
			}
			calc_neg(e[i].to,root);
		}
		return;
	}
	ans[now]=ask(1,n-(size[now]<<1),n-(max_subtree[now]<<1));
	for(int i=head[now];i;i=e[i].next)
	{
		if(e[i].to==father)
		{
			continue;
		}
		calc_neg(e[i].to,now);
	}
	ans[now]-=ask(1,n-(size[now]<<1),n-(max_subtree[now]<<1));
}

void calc_pos()//positive contribution
{
	for(int i=1;i<=n;++i)
	{
		if(i==root)
		{
			ans[i]+=ask(1,0,n-(size[mx]<<1));
			continue;
		}
		ans[i]+=ask(1,n-(size[i]<<1),n-(max_subtree[i]<<1));
	}
}

int x,y;
long long ans_sum;
void solve()
{
	n=read();
	memset(head,0,sizeof(head));
	for(int i=1;i<n;++i)
	{
		x=read();
		y=read();
		add_edge(x,y,(i<<1)-1);
		add_edge(y,x,(i<<1));
	}
	find_centroid(1,0);
	root=centroid;
	calc_size(root,0);
	build(1,0,n);
	calc_neg(root,0);
	calc_pos();
	ans_sum=0;
	for(int i=1;i<=n;++i)
	{
//		printf("%d ",ans[i]);
		ans_sum+=1ll*ans[i]*i;
	}
	printf("\n%lld\n",ans_sum);
}

int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	short T=read();
	while(T--)
	{
		solve();
	}
	return 0;
}