[zerojudge] b967: 第 4 題 血緣關係

題目連結：

b967: 第 4 題 血緣關係

題意：

給定 $n$ 個成員，

接下來 $n \ - \ 1$ 行為其成員關係，

輸出最遠血緣距離。

解題策略：

這題和 c463: apcs 樹狀圖分析 (Tree Analyses) 概念類似，

可先參考這篇了解樹的概念。

關於這題的，

先找到根節點，
從根節點開始深度優先搜尋$(DFS)$，

遞迴每一個子節點，
紀錄其最高和次高，

將其加起來並和另一個變數 $ans$(要回傳的答案)比較，

搜尋完整棵樹，

$ans$ 即為答案。

程式碼參考：

$C++$：

$JUDGE\_RESULT$：$AC \ (1.7s, \ 23.1MB)$

#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#define _ ios::sync_with_stdio(false), cin.tie(nullptr);
#define endl '\n'
using namespace std;

class Tree {
private:
    struct node {
        int parent, h1, h2; // 父節點, 最高, 次高
        vector<int> child; // 子節點
        node(): parent(-1), h1(-1), h2(-1) {}
        ~node() {
            child.clear();
        }
    };

    void find_root() { // 尋找根節點
        for (int i = 0; i < v.size(); i++)
            if (v[i].parent == -1) { // 根節點沒有父節點
                root = i;
                break;
            }
    }

    int dfs(int cur, int dep = 0) {
        if (!v[cur].child.size()) { // 為葉節點
            return dep;
        }
        int maxheight = -1;
        for (const auto& i : v[cur].child) {
            int tmp = dfs(i, dep + 1); //該層高度
            maxheight = max(maxheight, tmp); // 紀錄最大高度
            tmp = tmp - dep; // 當層高度
            // 紀錄最高 h1 和次高 h2
            if (tmp > v[cur].h1) {
                v[cur].h2 = v[cur].h1;
                v[cur].h1 = tmp;
            }
            else if (tmp > v[cur].h2) {
                v[cur].h2 = tmp;
            }
        }
        // 紀錄最遠關係
        // 如果 h2 不等於 -1, 那就 h1 + h2; 反之 h1 + 0
        ans = max(ans, v[cur].h1 + (v[cur].h2 == -1 ? 0 : v[cur].h2));
        return maxheight;
    }

    vector<node> v;
    int root, ans;
public:
    void update(int num, int val) {
        v[num].child.push_back(val); // 存取子節點
        v[val].parent = num; // 紀錄父節點
    }

    int furthest_relative() {
        if (root == -1)
            find_root();
        dfs(root); // 從根節點開始深度優先搜尋(DFS)
        return ans;
    }

    Tree(int n = 0): root(-1), ans(-1) {
        v.resize(n);
    }

    ~Tree() {
        v.clear();
    }
};

int main() { _
    for (int n, a, b; cin >> n;) {
        Tree tree(n);
        while (--n) {
            cin >> a >> b;
            tree.update(a, b);
        }
        cout << tree.furthest_relative() << endl;
    }
}

以上，
若有更好的想法歡迎提出哦！