DMOPC '17 Contest 1 P6 - Land of the Carrot Trees

View as PDF

Submit solution



Points:20 (partial)
Time limit:10.0s
Memory limit:256M
Authors:

Problem type

A long time ago, in the not-so-distant LCT (land of the carrot trees), where carrots grow on trees, lived a magical carrot. In this magical land, there were N cities numbered 1, 2, \ldots N, connected with N-1 roads, with no cycles. Over the course of Q days, some interesting things happened to the roads:

  • A x y z: A new road of durability z is built between cities x and y
  • R x y: The road between cities x and y is destroyed by a rampaging rabbit (it is guaranteed to exist prior to the operation)
  • Q x y: The eccentric king demanded to know the XOR of the durability of all roads on the path between cities x and y

It is guaranteed that there will be at most one path between any two cities at any point in time.

Can you help the people of LCT by implementing a program to simulate these events?

Constraints

For all subtasks, the durability of a path will be a positive integer in the range [1, 10^6].

Subtask 1 [20%]

1 \le N \le 1\,000
1 \le Q \le 1\,000

Subtask 2 [80%]

1 \le N \le 10^5
1 \le Q \le 10^5

Input Specification

The first line of input will have two integers, N and Q.
The next N - 1 lines will contain three integers, a_i,\text{ }b_i,\text{ }c_i, indicating there is a road of durability c_i between cities a_i and b_i.
The next Q lines will each contain a valid query.

Output Specification

For each Q query, print the answer to it on a new line. If the two cities are not connected, output -1.

Sample Input 1

5 4
1 2 3
2 4 5
3 5 6
2 3 8
R 3 2
A 3 1 6
Q 5 4
Q 3 2

Sample Output 1

6
5

Sample Input 2

6 8
1 2 3
3 4 5
4 5 6
4 1 8
6 1 4
Q 6 5
Q 3 2
R 4 3
R 4 1
A 1 3 8
Q 3 2
Q 4 5
Q 6 1

Sample Output 2

10
14
11
6
4

Comments


  • 0
    r3mark
     commented on Oct. 10, 2017

    In the case that the two cities are not connected, output -1. The problem statement has been adjusted accordingly.