apcs 樹狀圖分析 解答

請原諒我的錯字><

樹

樹是資料結構的一種，有很一些性質，不過這題要知道的只有「根」。根在樹中就是最上面的那一個點，也就是沒有父節點的那個點。

輸出跟節點編號

這題第一個部份是要輸出跟節點編號，方法是每個點紀錄他是否有父節點，在輸入完所有節點的關係後，沒有父節點的就是根喔。

輸出

$H(X)$

$H(x)$ 定義是

$\sum h(x)$， 因此我們需要先求

$h(x)$。h(x) 定義是在

$x$ 底下， 離

$x$ 最遠的節點距離。

可以從離根最遠的節點開始計算答案，往回推算。每個節點的

$h(x)$ 就是他底下所有節點的

$h(x)$。

而

$H(x)$ 也可以用類似方法，每個節點

$H(x)$ 就是他底下所有節點的

$H(x)$ 合加上本身的

$h(x)$。

實作

存圖

第一個實作上問題是存圖，你需要把題目給的樹資訊記錄下來。我們可以使用 vector 存每個節點的所有小孩。 (vector 是 c++ 可以動態變大的陣列)

for (ll j = 1; j <= sz; j++) {
    cin >> child;
    edge[i].push_back(child);
    has_par[child] = true;
}

可以用 for loop 取得一個點所有小孩

for (auto child : edge[current]) {
    /* do something*/
}

求答案

求答案可以用遞迴的技巧，在圖上遞迴的演算法叫做 DFS，他的概念是「相信」呼叫一個函數可以找出所有小孩的

$h(x)andH(x)$，所以每個點要找答案就先用那個函數找出自己所有小孩的答案，再用先前提到的方法求出答案。

void dfs(ll current) {
    for (auto child : edge[current]) {
        dfs(child); // 相信他會找出 h[chlid],, H[child]
        
        // 照定義求 h[current], H[current]
        h[current] = max(h[current], h[child] + 1);
        H[current] += H[child];
    }
    
    H[current] += h[current]; // 記得加上自己的 h(x)
}

附上會 AC 的 Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; // 避免 overflow
const ll MAXN = 100005;

ll n, h[MAXN], H[MAXN];
bool has_par[MAXN];
vector<ll> edge[MAXN];

void dfs(ll current) {
    for (auto child : edge[current]) {
        dfs(child);
        h[current] = max(h[current], h[child] + 1);
        H[current] += H[child];
    }
    H[current] += h[current];
}

/********** Good Luck :) **********/
int main()
{
    cin.tie(0); // 讓你程式跑更快

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        ll sz, child;
        cin >> sz;
        for (ll j = 1; j <= sz; j++) {
            cin >> child;
            edge[i].push_back(child);
            has_par[child] = true;
        }
    }

    ll root = -1;
    for (ll i = 1; i <= n; i++) {
        if (has_par[i] == false) {
            root = i;
        }
    }

    dfs(root);

    cout << root << endl << H[root] << endl;
    return 0;
}