b967: 第 4 題 血緣關係 解題心得

zerojudge題目網址：https://zerojudge.tw/ShowProblem?problemid=b967
題目來源：APCS考題
題目網址：
https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnx6c2dpdGl0aXR8Z3g6NDQ4NmIyNzljY2Q2N2ZiYg

解題策略：
將這棵樹視為無向樹，從任一起點出發，找尋離自己最遠的兩個端點，且不能經過重複的點，將距離相加就是答案，例如以０為起點，０１５＋０３６或０１４＋０３６距離都是２，所以２＋２＝４，或者以１為起點出發。１４＋１０３６或１５＋１０３６距離為１＋３＝４。
為了完成上面解法，在收測資的時候需要讓每個端點都知道自己可以到哪幾個端點。

程式碼如下：
有任何問題歡迎留言或私我或是ＭＡＩＬ給我。

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> nodes;
vector<int> book;
int ans;


int dfs(int now, int last_steps) {
    book[now] = 1;
    int dis1 = 0 , dis2 = 0 , dis;
    for (int x : nodes[now]) {
        if (!book[x]) {
            dis = dfs(x, last_steps + 1) + 1;
            if (nodes[now].size() == 0) continue;
            if (dis >= dis1) {
                dis2 = dis1;
                dis1 = dis;
            }
            else if (dis > dis2) {
                dis2 = dis;
            }
        }
    }
    ans = max(max(ans, dis1 + dis2), dis1 + last_steps);
    return dis1;
}

int main() {
    cin.tie(0),cin.sync_with_stdio(false);
    int n, a, b;
    while (cin >> n) {
        ans = 0;
        nodes.clear();
        nodes.resize(n);
        book.assign(n, 0);
        for (int i = 1; i < n; i++) {
            cin >> a >> b;
            nodes[a].push_back(b);
            nodes[b].push_back(a);
        }
        dfs(0, 0);
        cout << ans << "\n";
    }
}