CF1406C Link Cut Centroids

SunnyYuan的博客 / 2024-08-08 / 原文

思路

如果一棵树有两个重心，那么从一个重心的一边切割一个点到另外一个重心即可。

如果一棵树只有一个重心，那么随意断掉一个点再恢复即可。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct edge {
	int to, next; 
} e[N * 2];

int head[N], idx = 1;

void add(int u, int v) {
	idx++, e[idx].to = v, e[idx].next = head[u], head[u] = idx;
}

int sz[N];
int n;
int mx[N];
vector<int> ans;

void getroot(int u, int fa) {
	sz[u] = 1;
	mx[u] = 0;
	for (int i = head[u]; i; i = e[i].next) {
		int to = e[i].to;
		if (to == fa) continue;
		getroot(to, u);
		mx[u] = max(mx[u], sz[to]);
		sz[u] += sz[to];
	}
	mx[u] = max(mx[u], n - sz[u]);
	if (mx[u] * 2 <= n) {
		ans.push_back(u);
	}
}

int del_edge, last;

void dfs(int u, int fa) {
	// cout << u << ' ' << fa << endl;
	last = u;
	for (int i = head[u]; i; i = e[i].next) {
		int to = e[i].to;
		if (to == fa) continue;
		del_edge = i;
		dfs(to, u);
	}
}

void solve() {
	memset(head, 0, sizeof(int) * (n + 10));
	memset(mx, 0, sizeof(int) * (n + 10));
	idx = 1;
	ans.clear();
	
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		add(x, y), add(y, x);
	}
	getroot(1, 0);
	if (ans.size() == 1) {
		cout << e[3].to << ' ' << e[2].to << '\n';
		cout << e[3].to << ' ' << e[2].to << '\n';
	}
	else {
		del_edge = 0;
		dfs(ans[0], ans[1]);
		cout << e[del_edge].to << ' ' << e[del_edge ^ 1].to << '\n';
		cout << e[del_edge].to << ' ' << ans[1] << '\n';
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}