某岛

… : "…アッカリ～ン . .. . " .. .

July 10, 2013

BZOJ 3083. 遥远的国度

… 动态维护一棵点权有根树。。支持以下操作：

1 u

2 x y v

x->y

v

3 u

u

。。原生动态树无法支持子树操作，DFS() 序列无法支持路径操作。。。
… 但是树链剖分后，一段路径在 DFS() 序列中被分割成不超过 logn 段区间。。。。
。。因此可以直接用 DFS() 序列做。。

至于换根操作。。。以下来自何老师的原文。。。

PS：对于换根，ETT不用换根的，对于要换根的题，可以这么考虑，查询u的时候，如果新的根在u的上方，u的子树就是原来那个子树，如果新的根是u，就是整个树，如果新的根v是在u下面，只要找到u到v路径上的第一个结点，也就是u的孩子，u新的子树就是去掉这个点所在子树剩下的那些。

虽然以上是在说 ETT。。但是这里也是一样的。。）

。。。另。BZOJ 上数据太大 cin 会 RE。。（似乎是 HUSTOJ 的 judge 限制了 xxxx 的调用次数。？。。
不深究。。参见 https://gist.github.com/lychees/5958321

Posted by xiaodao
Category: 日常

July 10, 2013

切……都不提一下窝的n log^2 n会t的lct……= 3= /$:T_T

ysymyth

December 21, 2013

那啥。。。你的程序好像wa了。。。

December 16, 2014

/$:Orz /$:Orz /$:Orz /$:Orz /$:Orz /$:Orz /$:Orz /$:Orz /$:Orz /$:Orz /$:Orz /$:Orz /$:Orz /$:Orz /$:Orz