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 ”,其含义见题目描述部分。

    输出格式

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

    样例输入 1


    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 

    样例输出 1


    2
    1
    4
    2

    样例输入 2

    1
    20 12 20
    412060525 42425138 67114752 160822495 201962681 926214957 380263349 733667141 869039239 641017702 154667400 461702107 438851950 176272938 209229857 985208975 762952138 936593832 409183276 999506034
    2 17
    4 1
    15 3
    3 10
    9 10
    7 16
    19 15
    13 2
    6 2
    3 14
    7 18
    8 15
    Q 6 17 2
    Q 762952152 762952154 762952139
    L 380263329 380263352
    L 380263357 380263333
    Q 380263356 380263359 380263348
    L 641017709 641017703
    L 641017716 641017700
    Q 641017716 641017704 641017698
    Q 380263359 380263357 380263345
    L 733667140 733667136
    L 733667150 733667156
    L 733667145 733667142
    Q 733667149 733667145 733667140
    Q 67114772 67114761 67114759
    Q 733667145 733667159 733667142
    Q 380263359 380263356 380263351
    Q 869039233 869039232 869039237
    Q 380263359 380263345 380263356
    Q 733667136 733667140 733667143
    Q 412060537 412060516 412060519

    样例输出 2

    762952138
    380263349
    641017702
    380263349
    733667141
    67114752
    733667141
    380263349
    869039239
    380263349
    733667141
    412060525
    985208975

    提示

    对于第一个操作 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。之后的操作类似。