A distant country
###
Description
给出一棵树,需要支持换根、区间查询、区间修改等操作。
Solution
除了换根操作,其他都是树链剖分板子。
对于换根操作,我们考虑先以一号节点为根节点做一次树剖,然后对于换根的操作分类讨论。
接下来以 root 表示目前的根节点, x 表示 x 子树。
1. x==root
对于这种情况,根就是全局最小值,直接输出根即可。
2. x∈root⋂root∈1 | x∉root⋂x≠root⋂x∉(1→root)
对于这种情况,哪个为根对于 x 子树没有影响,所以直接查询。
3. x∈(1→root)
当 x 在它们所属的链上时,x 的子树就是除去往 root 方向的子树以外的所有子树。
所以把这些不去要的节点找出并去掉,就是答案了。
看下图,感性理解一下。
Code:
1 |
|