Link Cut Centroids—CF1406C

• 一棵树只能有 $1$ 个或 $2$ 个重心。当这棵树有两个重心的时候，这两个重心相邻（通过一条边直接相连）。

本题考查了树的深度优先遍历、一点点思维和上边这个性质。

$Code$

#include <bits/stdc++.h>
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 1e5 + 10;

int n;
int he[N], ed[2*N], ne[2*N], idx;
int st[N];
int res = N;
int found_res;
int center[5], len; // 记录重心(1个或两个重心)

void add(int a, int b) {
	ed[idx] = b, ne[idx] = he[a], he[a] = idx ++;
}

int dfs(int u) {
	st[u] = 1;
	int sum = 1;
	int res_now = 0;
	for (int i = he[u]; i != -1; i = ne[i]) {
		int j = ed[i];
		if (st[j] == 0) {
			int s = dfs(j);
			sum += s;
			res_now = max(res_now, s);
		}
	}
	res_now = max(res_now, n - sum);
	if (found_res) {
		// 第二次调用dfs函数的时候进入这里
		if (res_now == res) {
			center[++ len] = u;
		}
	} else {
		// 第一次调用dfs函数的时候进入这里
		res = min(res, res_now);
	}
	return sum;
}

void solve() {
	cin >> n;
	memset(he, -1, sizeof he);
	idx = 0;
	for (int i = 1; i <= n - 1; i ++) {
		int x, y; cin >> x >> y;
		add(x, y);
		add(y, x);
	}
	
	fill(st, st + n + 1, 0);
	
	res = N;
	found_res = 0;
	len = 0;
	dfs(1);
	
	found_res = 1;
	fill(st, st + n + 1, 0);
	dfs(1);
	
	if (len == 1) { // 一个重心，随便删除一条边再重新连接即可
		int a = 1;
		int edge = he[a];
		int b = ed[edge];
		cout << a << ' ' << b << "\n";
		cout << a << ' ' << b << "\n";
	} else {
		/*
		  两个重心，这种情况是本题的重点。
		  这时候我们要考虑删除一条边，再连接一条边。
		  
		  设两个重心分别为a, b;
		  那么分别删除这两个点后，剩余各个联通块中点数的最大值
		  一定是相等的。
		  我们需要让这两个数不相等，那么不难想到这种方法：
		  删除a所连接的一条边，再把这条边的另一个端点连接到b上。
		  （如果a只连接了b，那么对b进行上操作即可，因为题目中保证
		  一定有解）。
		  
		  这种方法保证a、b中其中一个所连的连通块的最大值减小，
		  另一个增大，而且其他点所连的连通块的最大值不变，
		  所以是可行的。
		 */
		int c1 = center[1], c2 = center[2];
		for (int i = he[c1]; i != -1; i = ne[i]) {
			int j = ed[i];
			if (j != c2) {
				cout << j << ' ' << c1 << "\n";
				cout << j << ' ' << c2 << "\n";
				return;
			}
		}
		for (int i = he[c2]; i != -1; i = ne[i]) {
			int j = ed[i];
			if (j != c1) {
				cout << j << ' ' << c2 << "\n";
				cout << j << ' ' << c1 << "\n";
				return;
			}
		}
	}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
	cin >> T; cin.get();
	while (T --) solve();
	return 0;
}