记录编号	595709	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2019S]树的重心	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	9.730 s
提交时间	2024-10-15 22:09:32	内存使用	18.60 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 3e5+10;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}


int n;


struct BIT{
	int c[N];
	void clear(){for(int i = 0;i <= n;i++)c[i] = 0;}
	int lowbit(int x){return x & (-x);}
	void add(int x,int val){
		if(x == 0)return;
		for(;x <= n;x += lowbit(x))c[x] += val;
	}
	int ask(int x){
		int ans = 0;
		for(;x > 0;x -= lowbit(x))ans += c[x];
		return ans;
	}
	int ask(int l,int r){
		if(l > r)return 0;
		return ask(r) - ask(l-1);
	}
}t;


int siz[N],mx[N],s[N],rt,m,se;
vector<int>e[N];
ll ans = 0,w[N];
struct Tree{
	void dfs(int x,int fa){
		siz[x] = 1,mx[x] = s[x] = 0;
		for(int y : e[x]){
			if(y == fa)continue;
			dfs(y,x);
			siz[x] += siz[y];
			s[x] = max(s[x],siz[y]);
			mx[x] = max(mx[x],siz[y]);
		}
		mx[x] = max(mx[x],n - siz[x]);
		if(mx[x] < mx[rt])rt = x;
	}
	void build(){
		mx[0] = 1e8,m = se = 0;
		int mx = 0;
		dfs(1,0),dfs(rt,0);
		dfs3(rt,0),dfs1(rt,0);
		for(int y : e[rt])if(siz[y] == s[rt])m = y;
		for(int y : e[rt])
			if(y != m && siz[y] > mx)mx = siz[y],se = y;
		dfs2(rt,0,0);
	}
	void dfs1(int x,int fa){
		if(x != rt)w[x] += (ll)x * t.ask(max(n - 2 * siz[x],0),max(0,n - 2 * s[x]));
		t.add(siz[x],-1);
		for(int y : e[x]){
			if(y == fa)continue;
			t.add(n - siz[y],1);
			dfs1(y,x);
			t.add(n - siz[y],-1);
		}
		t.add(siz[x],1);
	}
	void dfs3(int x,int fa){
		if(x != rt)w[x] += (ll)x * t.ask(max(n - 2 * siz[x],0),max(0,n - 2 * s[x]));
		t.add(siz[x],1);
		for(int y : e[x]){
			if(y == fa)continue;
			dfs3(y,x);
		}
		if(x != rt)w[x] -= (ll)x * t.ask(max(n - 2 * siz[x],0),max(0,n - 2 * s[x]));
	}
	void dfs2(int x,int fa,bool op){
		for(int y : e[x]){
			if(y == fa)continue;
			if(y == m)dfs2(y,x,1);
			else dfs2(y,x,op);
		}
		if(x != rt){
			if(op && 2 * max(siz[se],siz[m] - siz[x]) <= n - siz[x])ans += rt;
			if(!op && 2 * siz[m] <= n - siz[x])ans += rt;
		}
	}
}T;


void solve(){
	n = read();ans = 0,rt = 0;
	for(int i = 1;i <= n;i++)e[i].clear(),w[i] = 0;
	for(int i = 1;i < n;i++){
		int x = read(),y = read();
		e[x].pb(y),e[y].pb(x);
	}
	t.clear();
	T.build();
	for(int i = 1;i <= n;i++)ans += w[i];
	printf("%lld\n",ans);
}

int main(){
	freopen("2019centroid.in","r",stdin);
	freopen("2019centroid.out","w",stdout);
	int t = read();
	while(t--)solve();

	return 0;

}