4. 血緣關係

解題

這題是一個很明顯的圖論題目，那我們先使用講解資料結構:

• parent：所有節點的父節點，如果這個節點是root的話，就是-1
• child：所有節點的子節點，若這個子節點的child長度為0，這個節點則為leaf
• leaf：遍歷過child之後找到的leaf，以便進行樹狀結構運算(BFS)
• children：紀錄每個節點child的數量，以便運算是否可以進入queue進行BFS運算
• h：所有的節點高度

這題有個想法，當你一個節點下的子節點只有一個，那你就是這個節點的距離子節點+1，如果你節點下的子節點有兩個或以上，那就是取最長的兩個+2，這是尋找最長節點距離的方法

solve函數是在進行BFS運算，當queue的開頭為root代表所有的節點已經遍歷完成，如果沒有，那就把q繼續pop，如果這個節點下的子節點已經都被檢查過了($children_i=0$)，那我們就把這個節點加入BFS運算

AC Code

python

from sys import stdin
from collections import deque
import copy
n=int(stdin.readline().strip())
parent=[-1]*n
child=[[] for _ in range(n)]
for _ in range(n-1):
       a,b=map(int,stdin.readline().strip().split())
       parent[b]=a
       child[a].append(b)
children=[len(child[i]) for i in range(n)]

# 尋找葉子
leaf=[]
for i in range(len(child)):
    if len(child[i])==0:
        leaf.append(i)

        
def solve(children):
    q=deque(leaf)
    h=[0]*n
    while parent[q[0]]!=-1:
        x=q.popleft()
        children[parent[x]]-=1
        if children[parent[x]]==0:
            q.append(parent[x])
        h[parent[x]]=max(h[parent[x]],h[x]+1)
    return h


def main(h):
    max_num=0
    for i in range(len(child)):
        if len(child[i])==1:
            max_num=max(max_num,h[child[i][0]]+1)
        elif len(child[i])>=2:
            temp=[]
            for j in child[i]:
                temp.append(h[j])
            temp.sort()
            max_num=max(max_num,temp[-1]+temp[-2]+2)
    return max_num
print(main(solve(children)))

C++

#include<bits/stdc++.h>
using namespace std;
vector<int> solve(int n,const vector<int>& parent,vector<int>& children,const vector<int>& leaf){
    queue<int> q;
    for(int l : leaf){
        q.push(l);
    }
    vector<int> h(n,0);

    while(parent[q.front()]!=-1){
        int x=q.front();
        q.pop();

        int p=parent[x];
        if(p!=-1){
            h[p]=max(h[p],h[x]+1);
            children[p]--;
            if(children[p]==0){
                q.push(p);
            }
        }
    }
    return h;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin>>n;
    vector<int> parent(n,-1);
    vector<vector<int>> child(n);
    vector<int> children(n,0);
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        parent[b]=a;
        child[a].push_back(b);
        children[a]++;
    }
    vector<int> leaf;
    for(int i=0;i<n;i++){
        if(child[i].empty()){
            leaf.push_back(i);
        }
    }
    vector<int> h=solve(n,parent,children,leaf);
    int max_num=0;
    for(int i=0;i<n;i++){
        if(child[i].size()==1){
            max_num=max(max_num,h[child[i][0]]+1);
        }else if(child[i].size()>=2){
            vector<int> temp;
            for(int c:child[i]){
                temp.push_back(h[c]);
            }
            sort(temp.begin(),temp.end());
            int m=temp.size();
            max_num=max(max_num,temp[m-1]+temp[m-2]+2);
        }
    }
    cout<<max_num<<endl;
    return 0;
}