#37583: 解題思路(含一些小技巧)


edoctopus322@gmail.com (Moon Jam)

School : 臺北市立成功高級中學
ID : 167591
IP address : [36.225.19.60]
Last Login :
2023-12-23 13:47:18
b967. 4. 血緣關係 -- 2016年3月apcs | From: [36.225.13.17] | Post Date : 2023-09-17 21:29

 
解題思路:
這題是要求所謂的樹直徑(整個祖譜就可以看成是一顆樹,要求相距最遠就是樹直徑了)
我做這題的方法是在dfs遍歷整棵樹的同時,紀錄從葉子到各子樹的最大節點數(也就是那個節點到子葉的層數,後面稱為rank)以及各子樹的中最大直徑,同時取出各子樹中第一深跟第二深的為max_rank、second_rank,如此目前節點的直徑就會是:

max(children\_max\_distance, max\_rank+second\_rank+1)

(直觀想的話會以為該節點為根節點的樹直徑是第一深+第二深的層數+自己這個節點,但還要考慮到可能子樹中已經有更大直徑的狀況,還有只有一個節點、或本身就是葉子的狀況,但因為此時的second_rank或是max_rank、second_rank會是0,因此同樣會是max_rank+second_rank+1)

該節點的最大層數就會是子樹的最大層數+1(而當本身是葉子時就是1,但因為此時max_rank是0,因此這個special case寫的時候不用也不用特別限制)

另外我為了實作方便,我把max_distance獨立成一個變數,不跟dfs的遞迴寫在一起,這樣寫起來也比較簡單
其他更詳細的實作細節可以看底下程式碼的註解

🌟 如果確定時間複雜度是 O(n) 但還是TLE的話,有可能是你沒加上輸入輸出優化`ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);`,但這題好像有點刁鑽,所以可能還需要再快一些才會過,像是我後來就發現不能夠memset,因為不用每次都把整個陣列初始化,有要用到的再設回0就好了,另外也有人講到可以把cin/cout全部改成printf/scanf會更快,不過我是把memset改掉之後就成功AC了,或者你可以試試看多丟幾次,我丟上去AC的程式執行時間有差到快一秒的,可以多試幾次。
 
ZeroJudge Forum