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


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.217.8]
最後登入時間 ：
2024-04-13 22:06:23
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)

學校 : 國立臺灣科技大學
編號 : 153262
來源 : [114.136.159.95]
最後登入時間 ：
2023-07-29 13:10:41
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