#LAISIR41. 傳遞秘密的最長路徑

傳遞秘密的最長路徑

題目名稱:傳遞秘密的最長路徑

題目描述:

在一個龐大家族中,成員之間以親戚關係形成了一棵家族樹。某一天,編號為 rr 的成員得知了一個驚天大秘密,並希望透過家族成員逐步將秘密傳遞下去。

秘密的傳遞遵守以下規則:

  • 秘密只能從一位成員傳給與其有親戚關係的成員(即圖中的一條邊)
  • 每位成員最多只能參與一次秘密的傳遞(不能回傳)

請你計算,從成員 rr 開始,秘密最多可以連續傳遞幾次。


輸入格式:

第一行一個整數 nn2n1042 \leq n \leq 10^4),表示家族成員的總數(編號為 1 到 nn)。

接下來 n1n - 1 行,每行兩個整數 u,vu, v,表示成員 uuvv 有親戚關係。保證這些關係構成一棵連通無環圖(樹)。

最後一行一個整數 rr1rn1 \leq r \leq n),表示秘密的起始傳遞成員。


輸出格式:

輸出一個整數,表示秘密最多可以連續傳遞的次數(即從起點 rr 開始的最長路徑長度)。


輸入範例:

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。