---
tags: CSES題解
---

# CSES Problem Set — Concert Tickets 題解

## 題目
給定一顆有 $n$ 個節點的樹，你的目標是找到是*樹重心*，也就是若該節點為根，則所有子節點形成的子樹最多有 $\lfloor \frac{n}{2} \rfloor$ 個節點。

### 輸入
- 第一行有一個正整數 $n$，所有節點編號為 $1, 2, \ldots ,n$。($1 \leq n \leq 2 \times 10^5$)
- 接下來有 $n-1$ 行，每一行有兩個正整數 $u_i, v_i$，代表第 $u_i$ 跟第 $v_i$ 個節點之間有邊。($1 \leq u_i, v_i \leq n$)

### 輸出

輸出一個正整數代表是樹重心的節點，所有多個答案則輸出任意一個。

## 範例測資

Input:
5
1 2
2 3
3 4
3 5

Output:
3


## 想法
先備知識：[Subordinates](https://cses.fi/problemset/task/1674)。

已知我們可以透過 DFS 知道以 $1$ 為根時，再以每一個節點為根的子樹大小。（自己設做 $s_i$）


對於每個節點，$n-s_i$ 即為非子樹的大小，此時我們只需檢查他的每一個孩子的大小跟 $n-s_i$ 不會超過 $\lfloor \frac{n}{2} \rfloor$ 就代表是樹重心。

:::info
範例：
對節點 $3$ 來說，他要檢查 $s_4$、$s_5$ 跟 $n-s_3$（也就是節點 $1, 2$ 形成的子樹大小）是否超過 $\lfloor \frac{5}{2} \rfloor$，結果為真，引此它是樹重心。
:::

## 程式

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 2e5+10;

int n;
int u, v;
vector<vector<int>> G(MAX_N);
vector<int> subtree_size(MAX_N);

int dfs(int now, int pre){
    int ret = -1; // 如果還沒找到重心就回傳 -1
    bool check = true; // now 是否為重心
    subtree_size[now] = 1;

    for (auto x : G[now]){
        if (x==pre) continue;
        
        int res = dfs(x, now);
        if (res!=-1) ret = res;
        subtree_size[now] += subtree_size[x];
        if (subtree_size[x]>n/2) check = false;
    }
    if (n-subtree_size[now]>n/2) check = false;
    if (check) ret = now;

    return ret;
}

int main(){

    // input
    cin >> n;
    for (int i=0 ; i<n-1 ; i++){
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    // process
    int centroid = dfs(1, 0);

    // output
    cout << centroid << "\n";

    return 0;
}