Home => ProblemSet => 3.2-35:[SDOI2013] 森林
1964: 3.2-35:[SDOI2013] 森林
Time Limit: 2 Sec Memory Limit: 512 MB Submit: 0 Solved: 4[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
小 Z 有一片森林，含有 N 个节点，每个节点上都有一个非负整数作为权值。初始的时候，森林中有 M 条边。
小Z希望执行 T 个操作，操作有两类：
对于一个输入的操作 Q x y k，其真实操作为 Q x^lastans y^lastans k^lastans。
对于一个输入的操作 L x y，其真实操作为 L x^lastans y^lastans。其中 ^ 运算符表示异或，等价于 Pascal 中的 xor 运算符。
请写一个程序来帮助小 Z 完成这些操作。
小Z希望执行 T 个操作，操作有两类：
- Q x y k 查询点 x 到点 y 路径上所有的权值中，第 k 小的权值是多少。此操作保证点 x 和点 y 连通，同时这两个节点的路径上至少有 k 个点。
- L x y 在点 x 和点 y 之间连接一条边。保证完成此操作后，仍然是一片森林。
对于一个输入的操作 Q x y k，其真实操作为 Q x^lastans y^lastans k^lastans。
对于一个输入的操作 L x y，其真实操作为 L x^lastans y^lastans。其中 ^ 运算符表示异或，等价于 Pascal 中的 xor 运算符。
请写一个程序来帮助小 Z 完成这些操作。
Input
第一行包含一个正整数 testcase，表示当前测试数据的测试点编号。
第二行包含三个整数 N,M,T，分别表示节点数、初始边数、操作数。
第三行包含 N 个非负整数表示 N 个节点上的权值。
接下来 M 行，每行包含两个整数 x 和 y，表示初始的时候，点 x 和点 y 之间有一条无向边。
接下来 T 行，每行描述一个操作，格式为 Q x y k 或者 L x y，其含义见题目描述部分。
第二行包含三个整数 N,M,T，分别表示节点数、初始边数、操作数。
第三行包含 N 个非负整数表示 N 个节点上的权值。
接下来 M 行，每行包含两个整数 x 和 y，表示初始的时候，点 x 和点 y 之间有一条无向边。
接下来 T 行，每行描述一个操作，格式为 Q x y k 或者 L x y，其含义见题目描述部分。
Output
对于每一个第一类操作，输出一个非负整数表示答案。
Sample Input Copy
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
Sample Output Copy
2
2
1
4
2
HINT
样例解释：
对于第一个操作 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。之后的操作类似。
对于第一个操作 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。之后的操作类似。
