#LAISIR29. 神樹的最遠祝福

神樹的最遠祝福

🧮 題目:神樹的最遠祝福

📝 題目背景:

在遙遠的神族時代,每一位神靈都住在一個節點上,並透過神力通道彼此連接,這些通道構成了一棵神聖之樹。 神王每年都會舉行一次祝福儀式,將神力傳遞給最遠的一位神靈,象徵保護邊境。

為了預測祝福傳遞需要多少步,神族請你幫忙計算整棵神樹中,任意兩位神靈之間最長的距離,也就是這棵樹的直徑


🎯 任務說明:

給定一棵無向連通無環圖(即一棵樹),請你計算任意兩點間的最長距離,輸出該距離所經過的邊數


📥 輸入格式:

n
a₁ b₁
a₂ b₂
...
aₙ₋₁ bₙ₋₁
  • n 為節點數(1 ≤ n ≤ 10⁵)
  • 接下來 n-1 行,每行兩個整數 aᵢbᵢ,表示節點 aᵢ 與節點 bᵢ 間有一條邊

📤 輸出格式:

  • 一行一個整數,表示該樹的直徑(最長路徑所包含的邊數)

📘 範例輸入:

5
1 2
1 3
3 4
3 5

📗 範例輸出:

3

🧠 題解提示(可選):

你可以使用兩次 DFS 或 BFS:

  1. 從任一節點出發找到最遠節點 A;
  2. 再從 A 出發找到最遠的節點 B;
  3. A 與 B 間的距離即為樹的直徑。