C. Link Cut Centroids(求树的重心)_.net

C. Link Cut Centroids(求树的重心)

https://codeforces.com/contest/1406/problem/C

做这个题前提是要知道树的重心。百度拉了一下。

引用一下：https://blog.csdn.net/weixin_43810158/article/details/88391828

树的重心定义为树的某个节点，当去掉该节点后，树的各个连通分量中，节点数最多的连通分量其节点数达到最小值。树可能存在多个重心。如下图,当去掉点1后，树将分成两个连通块：（2,4,5），（3,6,7），则最大的连通块包含节点个数为3。若去掉点2，则树将分成3个部分，（4），（5），（1,3,6,7）最大的连通块包含4个节点；第一种方法可以得到更小的最大联通分量。可以发现，其他方案不可能得到比3更小的值了。所以，点1是树的重心。

性质：

　　1.删除重心后所得的所有子树，节点数不超过原树的1/2，一棵树最多有两个重心；

　　2.树中所有节点到重心的距离之和最小，如果有两个重心，那么他们距离之和相等；

　　3.两个树通过一条边合并，新的重心在原树两个重心的路径上；

　　4.树删除或添加一个叶子节点，重心最多只移动一条边；

5.一棵树最多有两个重心，且相邻。

思路：如果找到只有一个重心，那么直接删一个重心的直连边然后加回去就好了。

如果找到两个重心，那么在其中一个重心上找到一个直连点不是另一个重心，删除连另外一个就好了。

如何求树的重心？，

先任选一个结点作为根节点，把无根树变成有根树。然后设siz[i]表示以i为根节点的子树节点个数。转移为siz[i]=∑（siz[i的儿子节点] );

设son[i]表示删去节点x后剩下的连通分量中最大子树节点个数。其中一部分在原来i其为根的子树。son[i]=max(son[i],siz[i的儿子节点]);

另外一部分在i的“上方”子树有n-siz[i]个。 son[i]=max(son[i],n-siz[i]);

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
vector<LL>g[maxn]; 
LL siz[maxn],son[maxn];
LL r1,r2,n; 
void dfs(LL u,LL fa)
{
	siz[u]=1;
	son[u]=0;
	for(LL i=0;i<g[u].size();i++){
		LL v=g[u][i];
		if(v==fa) continue;
		dfs(v,u);
		siz[u]+=siz[v];
		son[u]=max(son[u],siz[v]);
	}
	son[u]=max(son[u],n-siz[u]);
	if((son[u]<<1)<=n) r2=r1,r1=u;
}
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  LL t;cin>>t;
  while(t--){
  	cin>>n;
  	for(LL i=0;i<=n+10;i++) g[i].clear(),siz[i]=0,son[i]=0;
  	for(LL i=1;i<n;i++){
  		LL x,y;cin>>x>>y;
  		g[x].push_back(y);g[y].push_back(x);
	}
	r1=r2=0;
	dfs(1,0);
	if(!r2){
		LL r3=g[r1][0];
		cout<<r1<<" "<<r3<<endl;
		cout<<r1<<" "<<r3<<endl;
	}
	else{
		LL r3=r1;
	//	debug(r1);debug(r2);
		for(LL i=0;i<g[r2].size();i++){
			r3=g[r2][i];
		//	debug(r3);
			if(r3!=r1) break;
		}
		cout<<r3<<" "<<r2<<endl;
		cout<<r3<<" "<<r1<<endl;
	}
  }
return 0;
}

本文地址：https://blog.csdn.net/zstuyyyyccccbbbb/article/details/108558682