#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:
- 從任一節點出發找到最遠節點 A;
- 再從 A 出發找到最遠的節點 B;
- A 與 B 間的距離即為樹的直徑。
Related
In following homework: