某島

… : "…アッカリ~ン . .. . " .. .
May 17, 2013

PKU Campus 2013

Problem F. Moles

Brief description:

… 動態維護一棵邊權樹, 支持單邊修改。。(邊權可以是負數)。。
。。以及詢問兩點之間的路徑長度,詢問某點到期子樹內一點的路徑長度的最大值。

Analysis:

… DFS 一遍。。得到。。
一個 Euler 序。。用來求 LCA 。。。
一個一進一出的 DFS 序 用來維護路徑。。
。。需要區間求和、和區間求最大前綴和兩類操作。。
。。這裡我們選擇線段樹。

。。。線段樹做第二問。。樹狀數組做第一問。。
。。線段樹同時解決兩問。。

External link:

http://poj.openjudge.cn/campus2013/