记录编号	547375	评测结果	AAAAAAAATTTEEEEEEEEE
题目名称	[CSP 2019S]树的重心	最终得分	40
用户昵称	Chtholly	是否通过	未通过
代码语言	C++	运行时间	14.338 s
提交时间	2019-12-03 13:57:07	内存使用	15.38 MiB

#include<bits/stdc++.h>
#define maxn 50005
using namespace std;
struct Node{
	int nex,to;
} a[maxn*2];
struct bian{
	int u,v;
} b[maxn];
int f[maxn],tot;
void Add_edge(int u,int v){
	a[++tot].nex=f[u],a[tot].to=v,f[u]=tot;
}
int size[maxn],vis[maxn];
int n,n1,n2;
long long ans;
void Find1(int x,int fa){
	n1++;
	for(int i=f[x];i;i=a[i].nex){
		int j=a[i].to;
		if(j==fa || vis[j]) continue;
		Find1(j,x);
	}
}
void Find2(int x,int fa){
	n2++;
	for(int i=f[x];i;i=a[i].nex){
		int j=a[i].to;
		if(j==fa || vis[j]) continue;
		Find2(j,x);
	}
}
void dfs(int x,int fa,int To){
	size[x]=1;int Max=-1;
	for(int i=f[x];i;i=a[i].nex){
		int j=a[i].to;
		if(j==fa || vis[j]==1) continue;
		dfs(j,x,To);
		Max=max(Max,size[j]);
		size[x]+=size[j];
	}
	Max=max(Max,To-size[x]);
	if(Max<=(To/2)) ans+=x;
}
void work(){
	scanf("%d",&n);
	memset(f,0,sizeof(f));tot=0;ans=0;
	for(int i=1;i<n;i++){
		scanf("%d%d",&b[i].u,&b[i].v);
		Add_edge(b[i].u,b[i].v);
		Add_edge(b[i].v,b[i].u);
	}
	for(int i=1;i<n;i++){
		n1=n2=0;
		vis[b[i].u]=vis[b[i].v]=1;
		Find1(b[i].u,0);Find2(b[i].v,0);
		memset(size,0,sizeof(size));
		dfs(b[i].u,0,n1);
		memset(size,0,sizeof(size));
		dfs(b[i].v,0,n2);
		vis[b[i].u]=vis[b[i].v]=0;
	}
	cout<<ans<<'\n';
}
int main()
{
	freopen("2019centroid.in","r",stdin);
	freopen("2019centroid.out","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--) work();
}