#P3306. 树

    ID: 2493 传统题 1000ms 256MiB 尝试: 1847 已通过: 376 难度: 6 上传者: 标签>CF1900普及+/提高-子树转区间普通线段树树上倍增动态换根补集转化

树

题目描述

一棵有根点权树有 nn 个结点,编号为 11 的结点是根节点,第 ii 个结点的父亲结点为 fif_i,权值为 viv_i。

接着进行 QQ 次以下操作:

  • V x  y\texttt{V }x\ \ y 表示将点 xx 的权修改为 yy;
  • E x\texttt{E }x 表示把有根树的根改为点 xx;
  • Q x\texttt{Q }x 表示查询点 xx 的子树最小值。

输入格式

第一行两个整数 n,Qn,Q。

接下来 nn 行,每行两个整数 fi,vif_i,v_i。

接下来 QQ 行,每行一次操作。

输出格式

对于每次 Q\texttt{Q} 操作,输出子树最小值。

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
1
2
3
4

数据规模与约定

对于 100%100\% 的数据,1≤n,Q≤1051\leq n,Q\leq 10^5,0≤fi≤n0\leq f_i\leq n,当且仅当 i=1i=1 时 fi=0f_i=0,0≤vi≤1040\leq v_i\leq 10^4。