TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5658
  • Problem
  • P5658
    Limits : Time Limit : 5000 MS   Memory Limit : - KB
    Judgment Tips : 1s,256m
    Description

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

    Input Format

    第一行两个整数 n, m ,分别表示树的大小和操作数。
      接下来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 Format

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

    Sample Input 1

    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

    1
    2
    3
    4

    Sample Input 2

    3 5
    0 1
    1 1
    2 1
    V 2 3
    V 2 3
    V 1 2
    E 3
    Q 3

    Sample Output 2

    1

    Hint

    对于 100% 的数据:\(n, m ≤ 10^5\)


    Source  bzoj3306