昨天想了半天想不出來，早早睡覺，一早起來突然頓悟了XD
題目就是給你一棵有權重的樹（單向，只能向葉子走），然後給定每一點的K值，代表可以走的距離，問哪個點可以被最多點走到。（節點數 <= 200000 ）
原本一直在想要怎麼把前面的K值全部扣掉當前距離，結果發現根本不需要這樣，因為直接反過來用加的就可以了XD。
原本：K1-d1-d2, K2-d2, K3
等價於
後來：K1 , K2+d1, K3+ d1+ d2
其實就這樣啦，那時候本來想要用 HEAP ，只是不會判斷如果有些點被丟掉之類的要怎麼辦，所以就直接離散化，寫BIT。
http://codepad.org/vohf3pqv
沒有留言:
張貼留言