Description

给定一棵大小为 n 的有根点权树,支持以下操作:
• 换根
• 修改点权
• 查询子树最小值

Input

第一行两个整数 n, Q ,分别表示树的大小和操作数。
接下来n行,每行两个整数f,v,第i+1行的两个数表示点i的父亲和点i的权。保证f < i。如 果f = 0,那么i为根。输入数据保证只有i = 1时,f = 0。
接下来 m 行,为以下格式中的一种:
• V x y表示把点x的权改为y
• E x 表示把有根树的根改为点 x
• Q x 表示查询点 x 的子树最小值

Output

对于每个 Q ,输出子树最小值。

Sample Input

3 7
0 1
1 2
1 3
Q 1
V 1 6
Q 1
V 2 5
Q 1
V 3 4
Q 1

Sample Output

1
2
3
4

HINT

对于 100% 的数据:n, Q ≤ 10^5。

题解

摘自zyf的blog

我们先以1为根dfs并建立倍增数组，然后如果根换成了rt，然后要查询x子树内的最小值。我们分情况讨论：

1）若x==rt，则直接输出整棵树的最小值

2）若lca（x，rt）既不等于x那么直接输出x的子树内的最小值

3）若lca（x，rt）==x那么我们发现整棵树除了x向下走可以到达rt的子树之外全部成了x在rt为根下的子树，那我们把这棵子树中最接近x的节点y求出，在整个区间中踢掉y在1根下子树的范围即可。