C++

C++ - Link Cut Centroids

1016142506

Question portal

性质

  1. For all subtrees obtained after deleting the center of gravity, the number of nodes does not exceed 1/2 of the original tree. A tree has at most two centers of gravity; 2. The sum of the distances from all nodes in the tree to the center of gravity is the smallest. If there are two centers of gravity, then The sum of their distances is equal;
  2. Two trees are merged through an edge, and the new center of gravity is on the path of the two centers of gravity of the original tree;
  3. When a leaf node is deleted or added to the tree, the center of gravity moves only one edge at most;
  4. A tree can have at most two centers of gravity, which are adjacent to each other.

Ideas

If you find that there is only one center of gravity, just delete the direct edge connecting the center of gravity and add it back.
If two centers of gravity are found, then if you find a direct connection point on one of the centers of gravity and not the other center of gravity, just delete the other one.

How to find the center of gravity of a tree?
First select any node as the root node to turn the unrooted tree into a rooted tree. Then let siz[x] represent the number of subtree nodes with x as the root node. Transfer to siz[x] = Σ(i = 0; i <= v[x].size()) siz[v[x][i]] ; Let son[x] represent the remainder after deleting node x The maximum number of subtree nodes in the connected component. Part of it is in the original subtree of i which is the root. son[x] = max(son[x], siz[v[x][i]]) ; The other part has n – siz[x] subtrees “above” x. son[x] = max(son[x], n – siz[x]);

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<utility>
#include<cstring>
#include<iostream>
#define go(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
int t, n, sz[100010], f1, f2, son[100010];
vector<int> v[100010];
void dfs(int x, int fa) {
    sz[x] = 1;
    son[x] = 0;
    int len = v[x].size();
    go(i, 0, len - 1) {
        int to = v[x][i];
        if (to == fa)
            continue;
        dfs(to, x);
        sz[x] += sz[to];
        son[x] = max(son[x], sz[to]);
    }
    son[x] = max(son[x], n - sz[x]);
    if ((son[x] << 1) <= n) {
        f2 = f1;
        f1 = x;
    }//用性质1判断节点x是否为重心
}
int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        memset(sz, 0, sizeof sz);
        memset(son, 0, sizeof son);
        f1 = f2 = 0;
        go(i, 1, n)
            v[i].clear();
        go(i, 1, n - 1) {
            int x, y;
            cin >> x >> y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        dfs(1, 0);
        if (!f2)
            cout << f1 << ' ' << v[f1][0] << endl << f1 << ' ' << v[f1][0] << endl;
        else {
            int len = v[f2].size();
            go(i,0,len-1)
                if (v[f2][i] != f1) {
                    cout << f2 << ' ' << v[f2][i] << endl << f1 << ' ' << v[f2][i] << endl;
                    break;
                }
        }
    }
    return 0;
}

Post Reply