TOJ159 與大榕樹的邂逅

一中最有名的就是大榕樹了！
繼續來爬樹吧！

連結：TOJ159 與大榕樹的邂逅

題目：

N個點的樹(編號1~N)，M筆操作，點上有權重
每次操作分兩種

1. 改掉某個節點的權重
2. 從編號1走到某節點需要的花費，花費指經過的所有節點權重總和

所有操作結束後輸出剛剛計算的總花費

做法：

以1為root，利用時間戳記dfs做樹壓平，紀錄走入及走出x點的時間in[x], out[x]

並在時間上放值，in放+W，out放-W
從根走到x，in[1]~in[x]的值總和就是答案
dfs走訪子樹的順序不重要，因為out會加上-W，所以答案是對的

而且事實上只要u是v的祖先，in[u]~in[v]都會是對的
可以想想如果不是的話該怎麼做？(即求樹上任兩點距離)

因為要求動態連續和，用個BIT維護，要注意樹壓平後N變2N

複雜度O(N + MlogN)

code: