#P13767. [2019年备战北大冬令营]树

[2019年备战北大冬令营]树

树

又是人民群众喜闻乐见的数据结构构题!

题目想必大家都听说过。给定一棵有根树,支持 88 个操作:

  1. 令 xx 为树的根。
  2. Link - Cut:即把点 xx 的父亲改为 yy。
  3. 把点 xx 的权增加 vv。
  4. 查询点 xx 的权。
  5. 把 xx 到 yy 的路径上的所有点的权增加 vv。
  6. 查询 xx 到 yy 上的所有点的权的最小值。
  7. 把 xx 这棵子树中的所有点的权增加 vv。
  8. 查询 xx 这棵子树中所有点的权的最小值。

输入格式

第一行两个数 n,mn, m,表示树的大小为 nn,操作数为 mm。

接下来 nn 行,第 i+1i+1 行有两个数 f,vf, v,表示点 ii 的父亲是 ff,初始权值为 vv。保证 f<if<i。若 f=0f=0,则 ii 为根。

接下来 mm 行,每行为以下格式之一,且恰好与题目描述中的 88 个操作对应:

  1. E x
  2. LC x y
  3. CV x v
  4. QV x
  5. CP x y v
  6. QP x y
  7. CS x v
  8. QS x

保证所有操作合法。

输出格式

对于 QV、QP、QS,输出对应的答案。

Samples

6 10
0 620
1 540
2 719
3 8
4 740
1 234
CP 3 4 87
E 3
LC 2 4
QP 6 1
QV 6
CV 5 663
LC 6 5
QS 3
CS 4 328
QS 6
234
234
95
562

数据范围与规模

对于 100%100\% 的数据,满足 n≤105,m≤105n\le 10^5,m \le 10^5。