APCS 血緣關係 (zerojudge b967)

發表於 更新於 分類於 ， 閱讀次數： 文章字數： 649 所需閱讀時間 ≈ 2 分鐘

題目網址

下圖為家族的關係圖：0 是 7 的孩子， 1、2 和 3 是 0 的孩子， 4 和 5 是 1 的孩子， 6 是 3 的孩子。 可以發現最遠的親戚關係為 4 (或 5) 和 6，他們的” 血緣距離” 是 4 (4→1→0→3→6)。 血緣關係 給予任一家族的關係圖，請找出最遠的” 血緣距離”。

解題思路：
這題是要求所謂的 樹直徑（整個祖譜就可以看成是一顆樹，要求相距最遠就是樹直徑了） 我做這題的方法是在 dfs 遍歷整棵樹的同時，紀錄從葉子到各子樹的最大節點數（也就是那個節點到子葉的層數，後面稱為 rank）以及各子樹的中最大直徑，同時取出各子樹中第一深跟第二深的為 max_rank、second_rank，如此目前節點的直徑就會是：

\[max(children\_max\_distance, max\_rank+second\_rank+1)\]

（直觀想的話會以為該節點為根節點的樹直徑是第一深 + 第二深的層數 + 自己這個節點，但還要考慮到可能子樹中已經有更大直徑的狀況，還有只有一個節點、或本身就是葉子的狀況，但因為此時的 second_rank 或是 max_rank、second_rank 會是 0，因此同樣會是 max_rank+second_rank+1）

該節點的最大層數就會是子樹的最大層數 + 1 (而當本身是葉子時就是 1，但因為此時 max_rank 是 0，因此這個 special case 寫的時候不用也不用特別限制)

另外我為了實作方便，我把 max_distance 獨立成一個變數，不跟 dfs 的遞迴寫在一起，這樣寫起來也比較簡單 其他更詳細的實作細節可以看底下程式碼的註解

🌟 如果確定時間複雜度是 \(O(n)\) 但還是 TLE 的話，有可能是你沒加上輸入輸出優化 ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);，但這題好像有點刁鑽，所以可能還需要再快一些才會過，像是我後來就發現不能夠 memset，因為不用每次都把整個陣列初始化，有要用到的再設回 0 就好了，另外也有人講到可以把 cin/cout 全部改成 printf/scanf 會更快，不過我是把 memset 改掉之後就成功 AC 了，或者你可以試試看多丟幾次，我丟上去 AC 的程式執行時間有差到快一秒的，可以多試幾次。

APCS 血緣關係 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define Max 100001
using namespace std;

vector<int> edge[Max];
bool vis[Max];
int max_dis=0;

int dfs(int node){
    //我定義的dis是節點個數，因此在最後輸出時需要-1
    //小孩要回傳他到自己最深的層數，母親記錄子代最大血緣距離（小孩最大的前兩個相加）、自己到最深的距離(最深距離+1)
    //並拿去跟max_dis取max，終端條件是沒有小孩的節點，回傳1
    if(vis[node]) return 0;
    vis[node]=1;
    int child_max_rank=0, child_second_max_rank=0;
    for(int child : edge[node]){
        int rank=dfs(child);
        if(rank>child_max_rank) child_second_max_rank=child_max_rank,child_max_rank=rank;
        else if(rank>child_second_max_rank) child_second_max_rank=rank;
    }
    max_dis = max(max_dis,child_max_rank+child_second_max_rank+1);
    // cout << node << ' '<< child_max_rank << ' ' << child_second_max_rank << ' ' << max_dis << '\n';
    return child_max_rank+1; //加上自己到子代的那層
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    while(cin >> n){
        max_dis=0;
        for(int i=0; i<n; i++) edge[i].clear(), vis[i]=0; //因為節點事是0~n所以是<n而不是<n-1
        // memset(vis, 0, sizeof(vis)); 這裡用memset會TLE，應該就是說不用每次都把100001個都改掉
        for(int i=0, tmp1, tmp2; i<n-1; i++)
            cin>>tmp1>>tmp2, edge[tmp1].push_back(tmp2), edge[tmp2].push_back(tmp1);
            //雖然題目聽起來是有向圖，但為了後續dfs遍歷整棵樹，這邊就用無向圖紀錄，之後再定向即可
        dfs(0);
        cout << max_dis-1 << '\n';
    }
    return 0;
}
AC的Submission～