發表新討論
#24476: 解題思路


fire5386 (becaidorz)

b967. 4. 血緣關係 -- 2016年3月 apcs | From: [61.230.46.160] | 發表日期: 2021-02-23 21:14

先用dfs求出每一個節點到葉子的最長距離

求出後再用dfs求深度

令mx為當前血緣最遠距離

假如a節點沒有孩子，則不用比較

假如a節點只有一個孩子，則mx=max(mx, 節點a的深度)

假如a節點有>=2個孩子，則找出深度最深的兩個孩子 -> 假設m和n為a節點中兩個最深的節點，mx=max(mx, m+n)

最後輸出mx即可

 

完整程式碼：

https://66lemon66.blogspot.com/2021/02/zerojudge-b967-4-c.html

#34760: Re: 解題思路


vic20050418@gmail.com (Wen Vic)

b967. 4. 血緣關係 -- 2016年3月 apcs | From: [210.59.2.253] | 發表日期: 2023-04-14 13:08

先用dfs求出每一個節點到葉子的最長距離

求出後再用dfs求深度

令mx為當前血緣最遠距離

假如a節點沒有孩子，則不用比較

假如a節點只有一個孩子，則mx=max(mx, 節點a的深度)

假如a節點有>=2個孩子，則找出深度最深的兩個孩子 -> 假設m和n為a節點中兩個最深的節點，mx=max(mx, m+n)

最後輸出mx即可

 

完整程式碼：

https://66lemon66.blogspot.com/2021/02/zerojudge-b967-4-c.html

網頁不允許存取

ZeroJudge Forum