【思维】2019 ICPC 徐州 M. Kill the tree

题链

题目解析

求所有子树的重心；

  $1.$ 以 $u$ 为根节点的子树的重心，一定在 $u$ 的重儿子的重心到 $u$ 的路径上；
  $2.$ 一棵树的重心不会超过两个；

对每一棵子树跳它重儿子的重心就可以了；

代码实现

#include <bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
	#define gg(x) cout << #x << ": " << x << "\n";
	#define LL long long
	#define ULL unsigned long long
	#define Pair pair<int ,int >
	#define ls rt<<1
	#define rs rt<<1|1
	#define PI acos(-1.0)
	#define eps 1e-8
	#define fi first
	#define se second
	#define ll long long
	
const int mod = 998244353;
const int MAXN = 2e9;
const int MS = 200009;

int n,m;
vector<int > vc[MS];
int sz[MS], zson[MS], fa[MS];
int zx[MS][2];

void dfs(int u, int f){
	sz[u] = 1;
	fa[u] = f;
	for(auto v:vc[u]){
		if(v != f){
			dfs(v, u);
			sz[u] += sz[v];
			if(sz[v] > sz[zson[u]]) zson[u] = v;
		}
	}
}

void dfs2(int u, int f){
	for(auto v:vc[u]){
		if(v != f) dfs2(v, u);
	}
	zx[u][0] = u;
	if(zson[u]){
		int t = zx[zson[u]][0];
		while(sz[u]-sz[t]>sz[t]) t = fa[t];
		zx[u][0] = t;
		if(sz[u]-sz[t] == sz[t]) zx[u][1] = fa[t];
	}
}

void solve(){
	cin >> n;
	for(int i=2;i<=n;i++){
		int u,v; cin >> u >> v;
		vc[u].push_back(v);
		vc[v].push_back(u);
	}
	dfs(1, 0);
	dfs2(1, 0);
	for(int i=1;i<=n;i++){
		if(!zx[i][1]) cout << zx[i][0] << "\n";
		else cout << min(zx[i][0],zx[i][1]) << " " << max(zx[i][0],zx[i][1]) << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	int ce = 1;
//	scanf("%d",&ce);
//	cin >> ce;
	while(ce--) solve();

	return 0;
}