#LAISIR41. 傳遞秘密的最長路徑
傳遞秘密的最長路徑
題目名稱:傳遞秘密的最長路徑
題目描述:
在一個龐大家族中,成員之間以親戚關係形成了一棵家族樹。某一天,編號為 的成員得知了一個驚天大秘密,並希望透過家族成員逐步將秘密傳遞下去。
秘密的傳遞遵守以下規則:
- 秘密只能從一位成員傳給與其有親戚關係的成員(即圖中的一條邊)
- 每位成員最多只能參與一次秘密的傳遞(不能回傳)
請你計算,從成員 開始,秘密最多可以連續傳遞幾次。
輸入格式:
第一行一個整數 (),表示家族成員的總數(編號為 1 到 )。
接下來 行,每行兩個整數 ,表示成員 與 有親戚關係。保證這些關係構成一棵連通無環圖(樹)。
最後一行一個整數 (),表示秘密的起始傳遞成員。
輸出格式:
輸出一個整數,表示秘密最多可以連續傳遞的次數(即從起點 開始的最長路徑長度)。
輸入範例:
5
1 2
1 3
3 4
3 5
1
輸出範例:
2
說明:
以下為輸入樣例對應的樹結構:
1
/ \
2 3
/ \
4 5
從節點 1 開始,最長的傳遞路徑為:
- 1 → 3 → 4,長度為 2
- 或 1 → 3 → 5,長度為 2
因此輸出為 2。
Related
In following homework: