某岛

… : "…アッカリ~ン . .. . " .. .
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