連接的無向非循環圖中所有可能樹的高度

Question

給定具有N個節點的連通的無向非循環圖，如何在線性時間內找到跨越圖中所有節點的每棵樹的高度？

Answer 1

改寫：給出的無根樹T，計算，爲T，根樹T（V）由在V生根它源自T的高度的各頂點v

首先選擇任意的底部R對於T，產生T（r）。掃描T（r）葉到根，爲每個頂點v存儲以v爲根的T（r）的子樹的高度，掃描T（r）根到葉，計算每個頂點v， T中從v開始的最長路徑的長度不能訪問v（相對於T（r））的恰當後代。這第二步有點棘手;你需要計算v和它的兄弟姐妹的最大和第二大高度，這可以重複用於v的兄弟姐妹。 T（v）的高度是其兩個標籤的最大值。