某島

… : "…アッカリ~ン . .. . " .. .
July 10, 2013

BZOJ 3083. 遙遠的國度

Brief description:

… 動態維護一棵點權有根樹。。支持以下操作:

    1 u: 換根。
    2 x y v: 將 x->y 的路徑上的點權全部修改為 v
    3 u: 詢問 u 為根的子樹內的最小值。

Analysis:

。。原生動態樹無法支持子樹操作,DFS() 序列無法支持路徑操作。。。
… 但是樹鏈剖分後,一段路徑在 DFS() 序列中被分割成不超過 logn 段區間。。。。
。。因此可以直接用 DFS() 序列做。。

至於換根操作。。。以下來自何老師的原文。。。

PS:對於換根,ETT不用換根的,對於要換根的題,可以這麼考慮,查詢u的時候,如果新的根在u的上方,u的子樹就是原來那個子樹,如果新的根是u,就是整個樹,如果新的根v是在u下面,只要找到u到v路徑上的第一個結點,也就是u的孩子,u新的子樹就是去掉這個點所在子樹剩下的那些。

雖然以上是在說 ETT。。但是這裡也是一樣的。。)

https://gist.github.com/lychees/5960424

。。。另。BZOJ 上數據太大 cin 會 RE。。(似乎是 HUSTOJ 的 judge 限制了 xxxx 的調用次數。?。。
不深究。。參見 https://gist.github.com/lychees/5958321

External link:

http://www.lydsy.com/JudgeOnline/problem.php?id=3083