Link Cut Centroids

Created by LXC on Thu Mar 7 19:31:34 2024

https://codeforces.com/problemset/problem/1406/C

ranting: 1700

tag: constructive algorithms, dfs and similar, graphs, trees

problem

给定一棵节点数为 $n$ 的树 ， 删一条边然后加上一条边 ， 使得该树的重心唯一 。（删掉的边和加上的边可以是同一条）

第 $1$ 行一个正整数 $T$ ， 表示有 $T$ 组测试数据 ， 其中 $1\le T\le10^4$

对于每组测试数据 。

第 $1$ 行一个正整数 $n$ ， 表示该树有 $n$ 个节点 ， 其中 $3\le n\le 10^5$ 。

第 $2$ 行到第 $n$ 行每行两个正整数 $x,y$ ， 表示 $x$ 到 $y$ 有无一条无向边 ， 其中 $1\le x,y\le n$ 。

对于每一组测试数据 。

第 $1$ 行两个正整数 $x_1,y_1$ ， 表示删的边的端点为 $x_1,y1$ 。

第 $2$ 行两个正整数 $x_2,y_2$ ， 表示连的边的端点为 $x_2,y_2$ 。

对于每个测试点，保证 $\sum{n}\le10^5$。

solution

设$w_i$为i点所连接的连同分量中最大的一个。

那么拥有$w_i$最小的i就是重心。

只有一个重心，任选一个一条边删除再连上就行。

如果有多个中心，最多只有两个，设为x和y，那么x中的一个分量断开，再连到y上就行了。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n;
    vector<vector<int>> g(n+1);
    for (int i=1; i<n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    vector<int> son(n+1), w(n+1);
    function<int(int,int)> getson = [&](int x, int fa) {
        son[x] = 1;
        for (auto y:g[x]) {
            if (y == fa) continue;
            son[x] += getson(y, x);
        }
        return son[x];
    };  
    getson(1, -1);
    function<void(int,int)> dfs = [&](int x, int fa) {
        w[x] = n-son[x];
        for (auto y:g[x]) {
            if (y == fa) continue;
            dfs(y, x);
            w[x] = max(w[x], son[y]);
        }
    };
    dfs(1, -1);
    // cout << w << endl;
    int mn = 1;
    for (int i=1; i<=n; i++) if (w[i] < w[mn]) mn = i;
    vector<int> mv;
    for (int i=1; i<=n; i++) {
        if (w[mn] == w[i]) mv.push_back(i);
    }
    // cout << mv << "\n";
    if (mv.size() == 1) {
        cout << 1 << " " << g[1][0] << "\n";
        cout << 1 << " " << g[1][0] << "\n";
    } else {
        if (g[mv[0]][0] == mv[1]) swap(g[mv[0]][0], g[mv[0]][1]);
        cout << mv[0] << " " << g[mv[0]][0] << "\n";
        cout << mv[1] << " " << g[mv[0]][0] << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}