2012年3月31日 星期六

tioj 1712 Tentacle Tree

昨天想了半天想不出來,早早睡覺,一早起來突然頓悟了XD

題目就是給你一棵有權重的樹(單向,只能向葉子走),然後給定每一點的K值,代表可以走的距離,問哪個點可以被最多點走到。(節點數 <= 200000 )

原本一直在想要怎麼把前面的K值全部扣掉當前距離,結果發現根本不需要這樣,因為直接反過來用加的就可以了XD。

原本:K1-d1-d2, K2-d2, K3
                     等價於
後來:K1 , K2+d1, K3+ d1+ d2

其實就這樣啦,那時候本來想要用 HEAP ,只是不會判斷如果有些點被丟掉之類的要怎麼辦,所以就直接離散化,寫BIT。

http://codepad.org/vohf3pqv

沒有留言:

張貼留言