這道題先是浪費我半個下午做，做不出來有時好久看題解實現，氣死我了。

題意。

給定一張 \(N\) 點的樹，讓我們考慮斷掉每一條邊，統計分裂出的兩個子樹的重心編號和之和。

要求 \(O(nlogn)\) 或更優的時間復雜度。

做法

這個咋做呢？我們可以在 OIwiki 中發現一些關于樹的重心的神秘性質。

我這里粘貼 OIwiki 原文了。

• 一棵有根樹的重心一定在根結點所在的重鏈上。一棵樹的重心一定是該樹根結點重子結點對應子樹的重心的祖先。

這就非常的貼心了。

我們發現我們很好判斷了，若想知道一個點是不是重心，我們僅僅需要判斷它的重兒子和除它子樹以外的那一部分就行了。

既然判斷非常簡單了，我們就可以倍增來找了。

有多個怎么辦？重心有多個的話兩個必然是相鄰的，再加一個判斷就行了。

為了方便我們就從上往下倍增了，這樣我們往重兒子走處理起來會很方便。

至于斷邊的影響，我們可以單獨處理考上斷邊的倍增數組，把直接的下一個改成次重兒子不就行了。

這個樣子就好做多了，我們在 dfs 的時候就可以把每一條邊搞定。

代碼如下↓

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=4e6+315;
int T, n, totsize;
struct Node{
	int nxt, to;
}node[MN];
int head[MN], tottt;
void insert(int u, int v){
	node[++tottt].to=v;
	node[tottt].nxt=head[u];
	head[u]=tottt; return;
}
int jump[MN][21], fa[MN];
int siz[MN], tmpsiz[MN];
int secw[MN], ans=0;
void init(){
	for(int i=1; i<=n; ++i){
		head[i]=secw[i]=siz[i]=tmpsiz[i]=fa[i]=0;
		for(int j=0; j<=20; ++j) jump[i][j]=0;	
	}
}
void Pre(){
	for(int j=1; j<=20; ++j){
		for(int i=1; i<=n; ++i){
			if(jump[i][j-1]) jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}
}
void update(int u){
	for(int j=1; j<=20; ++j){
		if(jump[u][j-1])
			jump[u][j]=jump[jump[u][j-1]][j-1];
		else jump[u][j]=0;
	}
}
int query(int u, int rt){
	for(int i=20; i>=0; --i){
		if(jump[u][i]&&siz[rt]-siz[jump[u][i]]<=siz[rt]/2){
			u=jump[u][i];
		}
	}
	return u;
}
bool check(int u, int tot){
	return max(siz[jump[u][0]],tot-siz[u])<=tot/2;
}
void dfs1(int u, int father){
	tmpsiz[u]=1; fa[u]=father;
	for(int i=head[u];i;i=node[i].nxt){
		int v=node[i].to;
		if(v==father) continue;
		dfs1(v,u); tmpsiz[u]+=tmpsiz[v];
		if(tmpsiz[v]>tmpsiz[jump[u][0]]){
			secw[u]=jump[u][0];
			jump[u][0]=v;
		}else if(tmpsiz[v]>tmpsiz[secw[u]]){
			secw[u]=v;
		}
	}
	siz[u]=tmpsiz[u];
}
void dfs2(int u, int father){
	int now, sav=jump[u][0];
	for(int i=head[u];i;i=node[i].nxt){
		int v=node[i].to;
		if(v==father) continue;
		if(v==sav) jump[u][0]=secw[u];
		else jump[u][0]=sav;
		if(siz[father]>siz[jump[u][0]]) jump[u][0]=father;
		update(u); now=u;
		siz[u]=totsize-tmpsiz[v];
		siz[v]=tmpsiz[v];
		fa[u]=fa[v]=0;
		now=query(u,u);
		ans+=check(now,siz[u])*now+check(fa[now],siz[u])*fa[now];
		now=v; now=query(v,v);
		ans+=check(now,siz[v])*now+check(fa[now],siz[v])*fa[now];
		fa[u]=v; dfs2(v,u);
	}
	jump[u][0]=sav; siz[u]=tmpsiz[u];
	fa[u]=father; update(u);
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>T; while(T--){
		init(); cin>>n;
		for(int i=1,u,v; i<n; ++i){
			cin>>u>>v; insert(u,v); insert(v,u);
		}
		ans=0; dfs1(1,0); Pre();
		totsize=siz[1]; dfs2(1,0);
		cout<<ans<<'\n';
	}
	return 0;
}