TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2638
  • 题目
  • P2638【SDOI2013 R1 Day1】森林
    限制 : 时间限制 : 80000 MS   空间限制 : 565536 KB
    问题描述

    时限:4s

    输入格式

    第一行包含一个正整数testcase,表示当前测试数据的测试点编号。保证1≤testcase≤20。
    第二行包含三个整数N,M,T,分别表示节点数、初始边数、操作数。第三行包含N个非负整数表示 N个节点上的权值。
    接下来 M行,每行包含两个整数x和 y,表示初始的时候,点x和点y 之间有一条无向边,
    接下来 T行,每行描述一个操作,格式为“Q x y k”或者“L x y ”,其含义见题目描述部分。

    输出格式

    对于每一个第一类操作,输出一个非负整数表示答案。

    样例输入


    8 4 8
    1 1 2 2 3 3 4 4
    4 7
    1 8
    2 4
    2 1
    Q 8 7 3
    Q 3 5 1 
    Q 10 0 0 
    L 5 4 
    L 3 2 
    L 0 7 
    Q 9 2 5 
    Q 6 1 6 

    样例输出


    2
    1
    4
    2

    提示

    对于第一个操作 Q 8 7 3,此时 lastans=0,所以真实操作为Q 8^0 7^0 3^0,也即Q 8 7 3。
    点8到点7的路径上一共有5个点,其权值为4 1 1 2 4。
    这些权值中,第三小的为 2,输出 2,lastans变为2。
    对于第二个操作 Q 3 5 1 ,此时lastans=2,所以真实操作为Q 3^2 5^2 1^2 ,也即Q 1 7 3。
    点1到点7的路径上一共有4个点,其权值为 1 1 2 4 。
    这些权值中,第三小的为2,输出2,lastans变为 2。之后的操作类似。