夏晓光(loveJY)的博客

简要题意：

删去每个边之后树分裂成两个小树，然后对两棵树所有重心的编号求和，$n<=1e5$

首先我们考虑怎么快速求出某颗树的重心，可以调整法，就是沿着重儿子跳，保持满足$sum-siz[u]<=n/2$，而且u的重儿子大小小于$n/2$

那么我们发现这个东西可以倍增跳啊，如果此时除去重儿子子树其他点加起来数太小了，那么可以向重儿子跳，只要满足这个条件我们那就倍增向下跳，最后一定能落在重心上！

注意这个是因为我们断开了一条边，所以我们还要观察断开后siz和son的变化。。。

case1 处于断开边的下方

siz，son都不变，sum变了

case2 处于被断开边的上方

我们发现除了被断开边的上面那个点所在的重链要改改外其他的好像不太变？

而那个重链我们可以在换根的时候一并都改了，因为我们不存在一条过原来根到另个子树的重链

别的没什么了，就是注意处理倍增

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int MAXN=1e6+7;
namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE],*p1=buf,*pend=buf;
	inline char nc() {
		if(p1==pend) {
			p1=buf;
			pend=buf+fread(buf,1,BUF_SIZE,stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x=0;
		char s=nc();
		for(; !isdigit(s); s=nc());
		for(; isdigit(s); s=nc())x=(x<<1)+(x<<3)+s-'0';
		return x;
	}
}
using namespace fastIO;
int n;
int ccnt,home[MAXN],nxt[MAXN],to[MAXN];
#define ad2(x,y) (ct(x,y),ct(y,x))
inline void ct(int x,int y) {
	ccnt++;
	nxt[ccnt]=home[x];
	home[x]=ccnt;
	to[ccnt]=y;
}
int siz[MAXN],son[MAXN],p[MAXN][20],fa[MAXN],siz2[MAXN],son2[MAXN],son3[MAXN],pr[MAXN];
inline void dfs(int u,int F) {
	siz[u]=1;
	fa[u]=F;
	pr[u]=F;
	for(int i=home[u]; i; i=nxt[i]) {
		int v=to[i];
		if(v==F)continue;
		dfs(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son2[u]=son[u],son[u]=v;
		else if(siz[v]>siz[son2[u]])son2[u]=v;
		//son是最大子，son2是次大子
	}

	p[u][0]=son[u];
	for(int i=1; i<=17; ++i)p[u][i]=p[p[u][i-1]][i-1];//跳重儿子的倍增
}

ll ans;
inline int pd(int x,int sum) {
	return x*(max(siz2[son3[x]],sum-siz2[x])<=sum/2);
}

inline void dfs2(int u,int F) {
	for(int i=home[u]; i; i=nxt[i]) {
		int v=to[i];
		if(v==F)continue;

		siz2[u]=siz[1]-siz[v];//断开这条边并且u是根
		fa[v]=0;
		fa[u]=0;
		//两个都是根啊
		if(son[u]==v)son3[u]=son2[u];//如果是重儿子我们选择次儿子
		else son3[u]=son[u]; //如果是不重儿子，那么这个点重儿子就可以继承
		if(siz2[F]>siz2[son3[u]])son3[u]=F;//换成另一个方向

		p[u][0]=son3[u];
		for(int j=1; j<=17; ++j)
			p[u][j]=p[p[u][j-1]][j-1];
		//向上跳
		int b=u;
		for(int j=17; j>=0; --j)
			if(siz2[u]-siz2[p[b][j]]<=siz2[u]/2)b=p[b][j];
		ans+=pd(son3[b],siz2[u])+pd(b,siz2[u])+pd(fa[b],siz2[u]);
		//siz2[u]是最大,而且可能他或他的重儿子或者他的父亲都能做成重心
		//向下跳qwq
		b=v;
		for(int j=17; j>=0; --j)
			if(siz2[v]-siz2[p[b][j]]<=siz2[v]/2)b=p[b][j];
		ans+=pd(son3[b],siz2[v])+pd(b,siz2[v])+pd(fa[b],siz2[v]);

		fa[u]=v;
		dfs2(v,u);
	}
	son3[u]=p[u][0]=son[u];
	fa[u]=pr[u];
	for(int j=1; j<=17; ++j)
		p[u][j]=p[p[u][j-1]][j-1];
	siz2[u]=siz[u];
}

int main() {
//	freopen("test.in","r",stdin);
	int T;
	T=read();
	while(T--) {
		memset(home,0,sizeof(home));
		memset(son,0,sizeof(son));
		memset(fa,0,sizeof(fa));
		memset(pr,0,sizeof(pr));
		ccnt=0;
		ans=0;
		n=read();
		for(int i=1,x,y; i<n; ++i) {
			x=read();
			y=read();
			ad2(x,y);
//			ad2(y,x);
		}
		dfs(1,0);
		memcpy(siz2,siz,sizeof(siz2));
		memcpy(son3,son,sizeof(son3));
		memcpy(fa,pr,sizeof(fa));
		dfs2(1,0);
		printf("%lld\n",ans);
	}
}