Link Cut Centroids
题意
对于一棵树 删除一条边再加上一条边使得新树只有一个重心
思路
此题转换成求树的重心树的重心最多有两个且有边相连 所以可以分为以下两种情况
此树只有一个重心任找与重心相连的一条边 删除再加上即可
找到了两个重心a,b 任选其中一个 例如选a 删除掉与 a 的除 b 外任意一个邻点的一条边 然后将这个邻点连到b 上去
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1e9+7; #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } inline LL lowbit(LL x) { return x & -x; } const int N = 500010; int n; bool vis[N]; vector<int>v[N]; int t1, t2; //两个重心 int ans = INF; int son[N]; void init() { for (int i = 1; i <= n; ++i) { v[i].clear(); vis[i] = 0; son[i] = 0; } t1 = t2 = 0; ans = INF; } int dfs(int u) { vis[u] = true; int sum = 1, res = 0; for (int i = 0; i < v[u].size(); ++i) { int j = v[u][i]; if (!vis[j]) { int s = dfs(j); sum += s; res = max(res, s); } } res = max(res, n - sum); if (ans >= res) { ans = res; son[u] = res; t2 = t1; t1 = u; } return sum; } void solve() { cin >> n; for (int i = 1; i <= n - 1; ++i) { int a, b; scanf("%d%d", &a, &b); v[a].push_back(b); v[b].push_back(a); } dfs(1); //找树的重心 if (son[t1] != son[t2]) { printf("%d %d\n", t1, v[t1][0]); printf("%d %d\n", t1, v[t1][0]); } else { int u = 0; for (int i = 0; i < v[t1].size(); ++i) { int j = v[t1][i]; if (j != t2) { u = j; break; } } printf("%d %d\n", t1, u); printf("%d %d\n", u, t2); } init(); } int main() { int t; cin >> t; while(t--) solve(); return 0; }
