[Noip2019]树的重心

一.前言

真就一行代码调一天呗……题目链接

二.思路

首先题目暗示的很明显了，要你一条边一条边的拆开然后分开算。那么预估一下时间复杂度 (O(n^2))，还有 t 组数据，芜湖直接起飞。但是，如果我们骚一点，在每次找重心的方式上做一做文章，就可以将时间复杂度降到 (O(nlogn)),而这种骚办法，就是倍增。

首先我们要明确几个结论。

1.对于一个以 u 为根的子树，这颗子树的重心一定会在 u 的重链上（定义与树链剖分的相同，就是以它的某个儿子为根的子树大小最大时，那个儿子所在的方向），这个可以轻易的得出（设这个重心为 v，则有 (size[u]-size[v]<=lfloordfrac{size[u]}{2} floor),( herefore size[v]>=lfloorfrac{u}{2} floor),所以必然为重儿子），那么寻找重心的方向就已经确定了。

2.一个点是重心，那么这个点的重儿子或者父亲也有可能是重心（题目明示）

有了这两个结论后，我们试图做出暴力的方法。

暴力就是（对于一颗树），我们从它的根节点开始，不断地沿着重儿子的方向去找，直到找到重心为止，很暴力，很简单。而重心的判断条件题目已经给出(O(n^2))ok的。

但是我们要倍增奥，我们倍增去寻找一个深度最大的点v使得(size[u]-size[v]<=dfrac{size[u]}{2}),此时的v为这颗树的重心.最深的保证了它是重心的正确性（更浅的有可能儿子的子树大小超过限制），再结合结论 2 ，验一下他的父亲就ok了。然后倍增的方法在于，之前我们是不断沿着重儿子的方向找，现在我们一步跨大点，设 (g[x][i]) 为 x 向着重儿子方向走 (2^i) 步，这样就能 (O(logn)) 找到v。就基本解决了。第一次用一个 dfs 处理出重儿子和 g 就好。

然后此题另外一个很复杂的地方在于断开一条边之后，另一边的树换根了。假设断掉的边是 ((u,v)),且深度较浅的是 u ，所以 u 成了另外一个根。对于 v 来说，它可以沿用之前的 dfs 出的数据，很方便。但是 u 就比较离谱。

我愿称以 u 为根的那个树，叫反图（在代码中所有反图的数组都有前缀 ba_),很显然的，反图有着与原图十分重合的地方，可以自己画图感受一下，只要重儿子不变，g也是不会变的。由于构造反图与枚举边同时进行，我们使用dfs。

在这次dfs中，默认 u 以上的反图全部完毕。于是将 u 接到反图上面去，就会出现爸爸当儿子，儿子当爸爸的局面~~（就像男生寝室的混乱关系）~~，当然 dfs 完了之后，爸爸还是爸爸，儿子还是儿子……，这里看代码会清晰很多。然后对于 u 在反图上面倍增就好，维护反重儿子和反g。

三.CODE

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<fstream>
#include<cmath>
#include<cstring>
using namespace std;
#define m_for(i,x,y) for(int i=x;i<=y;++i)
int read(){
	char ch=getchar();
	int res=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())res=res*10+(ch-'0');
	return res*f;
}
const int MAXN=299999;
int t,n;
int head[MAXN],to[2*MAXN],ne[2*MAXN],tot;
void add(int x,int y){
	to[++tot]=y;
	ne[tot]=head[x];
	head[x]=tot;
}
void build(){
	int x,y;
	m_for(i,1,n-1){
		x=read();y=read();
		add(x,y);add(y,x);
	}
}
int f[MAXN],size[MAXN],heavy[MAXN],sc_heavy[MAXN],g[MAXN][18];
void dfs1(int x,int fa){
	f[x]=fa;size[x]=1;
	for(int i=head[x],v;i;i=ne[i]){
		v=to[i];
		if(v==fa)continue;
		dfs1(v,x);
		size[x]+=size[v];
		if(size[v]>size[heavy[x]])sc_heavy[x]=heavy[x],heavy[x]=v;
		else if(size[v]>size[sc_heavy[x]])sc_heavy[x]=v;
        //这里需要记录重儿子(heavy)和次重儿子(sc_heavy)在dfs2会用到次重儿子
	}
	g[x][0]=heavy[x];
	for(int i=1;i<=17;++i)g[x][i]=g[g[x][i-1]][i-1];//dp预处理
}
int ba_heavy[MAXN],ba_size[MAXN],ba_f[MAXN],ba_g[MAXN][18];
long long ans;
long long check(int x,int sum){
	return 1LL*x*(max(sum-ba_size[x],ba_size[ba_heavy[x]])<=(sum/2));//计算一个点的贡献
}
void dfs2(int x,int fa){
	for(int i=head[x],v;i;i=ne[i]){
		v=to[i];
		if(v==fa)continue;
		ba_size[x]=size[1]-size[v];//反图的大小用原图相减
		ba_f[x]=0;ba_f[v]=0;//各自为根
		if(v==heavy[x])ba_heavy[x]=sc_heavy[x];
        //如果对面就是重儿子，那么在反图的重儿子就是原图的次重儿子
		else ba_heavy[x]=heavy[x];
		if(ba_size[fa]>ba_size[ba_heavy[x]])ba_heavy[x]=fa;
        //原来的爸爸要变儿子，所以重儿子搞一搞
		ba_g[x][0]=ba_heavy[x];
		for(int i=1;i<=17;++i)ba_g[x][i]=ba_g[ba_g[x][i-1]][i-1];
        //dp算反图g
		int now=x;
        //倍增跑正反图
		for(int i=17;i>=0;--i)if(ba_size[x]-ba_size[ba_g[now][i]]<=(ba_size[x]/2))now=ba_g[now][i];
		ans+=check(now,ba_size[x])+check(ba_f[now],ba_size[x]);//检验它和它父亲
		now=v;
		for(int i=17;i>=0;--i)if(size[v]-size[g[now][i]]<=(size[v]/2))now=g[now][i];
		ans+=check(now,size[v])+check(f[now],size[v]);
		ba_f[x]=v;//爸爸变儿子
		dfs2(v,x);
	}
    //它的子树遍历完之后还原成原图
	ba_f[x]=f[x];
	ba_g[x][0]=ba_heavy[x]=heavy[x];
	for(int i=1;i<=17;++i)ba_g[x][i]=ba_g[ba_g[x][i-1]][i-1];
	ba_size[x]=size[x];
}
void clean(){
	ans=0;tot=0;
	memset(head,0,sizeof(head));
	memset(heavy,0,sizeof(heavy));
	memset(g,0,sizeof(g));
	memset(ba_g,0,sizeof(ba_g));
}
int main(){
	t=read();
	while(t--){
		n=read();
		clean();//初始化
		build();//建图
		dfs1(1,0);//处理原图
		memcpy(ba_heavy,heavy,sizeof(ba_heavy));//因为反图和原图相似所以copy过来
		memcpy(ba_size,size,sizeof(ba_size));
		memcpy(ba_f,f,sizeof(ba_f));
		memcpy(ba_g,g,sizeof(g));
		dfs2(1,0);
		printf("%lld
",ans);
	}
	return 0;
}