發表新討論
#25613: O(1)空間找樹根


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.217.8]
最後登入時間 ：
2024-04-13 22:06:23
b967. 4. 血緣關係 -- 2016年3月apcs | From: [61.230.21.219] | 發表日期 : 2021-06-06 22:09

兩個方法

方法一：

令root為0 ~ n - 1的加總(使用梯形公式，不過root要開long long因為加總會超過int上限)

接下來的n - 1行，將root 減去 b

最後root的值就是root的id

方法二：

同方法一，不過用xor運算(xor歸零律)，另外，root用int即可因為bi不超過int

 

找到樹根後用dfs走遍樹就可以找到最遠距離

 
#25615: Re:O(1)空間找樹根


s0254020@gm.ncue.edu.tw (鄭常仁)

學校 : 不指定學校
編號 : 155289
來源 : [220.133.172.118]
最後登入時間 ：
2021-06-07 10:25:58
b967. 4. 血緣關係 -- 2016年3月apcs | From: [220.133.172.118] | 發表日期 : 2021-06-07 10:14

我找樹根的方式是建立一個布林陣列(初始False)
for跑過每條線，把當小孩的人的打勾在布林陣列(改為True)

for跑過布林陣列，找出唯一沒有變成True的人就是根
給你參考w



 
#25625: Re:O(1)空間找樹根


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.217.8]
最後登入時間 ：
2024-04-13 22:06:23
b967. 4. 血緣關係 -- 2016年3月apcs | From: [61.230.21.219] | 發表日期 : 2021-06-07 19:51

這樣當然可以，我只是提供一個很省空間的做法而已

 
ZeroJudge Forum