Codeforces 1406C Link Cut Centroids 题解（树的重心）

题目：Codeforces

中文题面：洛谷

分类讨论重心的数量：

• 一个重心：随便断掉一条与边再连上。
• 两个重心：选一个重心，断掉一个与这个重心相连的点的边，然后将这个点与另一个重心连上。

怎么找树的重心可以参考：OI Wiki

代码（C++）：

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<vector<int>> graph;
vector<int> centroid;
vector<int> siz;
vector<int> weight;

// 寻找一个不为 fa 的点（一条边）
int find(int u, int fa) {
	for (int v : graph[u]) {
		if (v == fa) {
			continue;
		}
		return v;
	}
}

void dfs(int u, int fa) {
	siz[u] = 1;
	weight[u] = 0;
	for (int v : graph[u]) {
		if (v == fa) {
			continue;
		}
		dfs(v, u);
		siz[u] += siz[v];
		weight[u] = max(weight[u], siz[v]);
	}
	weight[u] = max(weight[u], n - siz[u]);
	if (weight[u] <= n / 2) {
		centroid[centroid[0] != 0] = u;
	}
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		cin >> n;
        
		// 二维vector这里一定要清空
		graph.clear();
		centroid.clear();
        
		graph.resize(n + 1, vector<int>());
		centroid.resize(2, 0);
		siz.resize(n + 1, 0);
		weight.resize(n + 1, 0);
	
		for (int i = 2; i <= n; i++) {
			int u, v;
			cin >> u >> v;
			graph[u].push_back(v);
			graph[v].push_back(u);
		}
		dfs(1, 0);
		if (centroid[1] == 0) {
			// 只有一个重心的情况
			int v = find(centroid[0], centroid[0]);
			cout << centroid[0] << " " << v << endl;
			cout << centroid[0] << " " << v << endl;
		} else {
			int v = find(centroid[0], centroid[1]);
			cout << centroid[0] << " " << v << endl;
			cout << centroid[1] << " " << v << endl;
		}
	}
	return 0;
}

PS：写这个是因为感觉洛谷里的题解个人看着有点复杂。