【筆記】樹重心 (Tree Centroid)

  • 【資料來源】資芽演算法班2020 (No. 293)
  • 給定一棵樹,如果把樹上的某一個節點及其所連的邊移除,我們會得到若干棵樹。例如下左圖為原始的樹,移除節點 2 之後就會變成如中間那張圖,而若移除節點 1則會變成如右邊那張圖。
  • 對於給定的一棵樹,我們定義拔除節點 x 的慘度為「拔除節點 x 後,形成的若干棵樹分別的節點數量中的最大值。」。舉例來說,上左圖拔除節點 2 之後,形成 2 棵樹,節點數量分別是 1 和 3,其中最大者為 3,因此該樹拔除節點 2 的慘度為 3。同理,該樹拔除節點 1 的慘度為 2。
  • 一棵樹,我們定義所有點當中,拔除它的慘度最小的點為「重心」。
  • 現在給你一棵樹,請你找出它的「重心」。
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 100005;
int N;
vector <int> g[maxn];
int cost[maxn]; //慘度

int dfs(int now, int pre){
    //tot: 以now為root的子樹size
    int tot = 1, ret = 0;
    // now下方的子樹
    for (auto nxt: g[now]){
        if (nxt != pre){
            ret = dfs(nxt, now);
            tot += ret;
            cost[now] = max(cost[now], ret);
        }
    }
    // now頭上的子樹
    cost[now] = max(cost[now], N - tot);
    return tot;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T, a, b;
    cin >> T;
    while (T--){
        cin >> N;
        for (int i = 0; i < N; i++){
            cost[i] = 0;
            g[i].clear();
        }
        for (int i = 0; i < N-1; i++){
            cin >> a >> b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        dfs(0, -1); //將0當作root
        int mn = 0x7FFFFFFF;
        int ans = -1;
        for (int i = 0; i < N; i++){
            if (cost[i] < mn){
                mn = cost[i];
                ans = i;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

分享本文 Share with friends