2023 Winter Waterloo Local Contest, Problem E
Your task is to maintain a colourful tree and process queries.
At the beginning, there is only one vertex numbered
0 x c d
: Add a new vertex indexed with colour to the tree, where is the current number of existing vertices. An edge connecting vertex and with length will also be added to the tree.1 x c
: Change the colour of vertex to .- After each operation, you should find a pair of vertices
and with different colours in the current tree so that the distance between and is as large as possible.
The distance between two vertices
Input Specification
There are multiple test cases. The first line of the input contains an integer
The first line of the input contains two integers
For the following
- If the
-th line contains integers , , and , the -th operation will add a new vertex with colour to the tree and connect it to vertex with an edge of length . - If the
-th line contains integers , and , the -th operation will change the colour of vertex to . - It's guaranteed that the sum of
of all test cases will not exceed .
Output Specification
For each operation output the maximum distance between two vertices with different colours. If no valid
pair exists output 0
instead.
Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!
Sample Input
2
1 1
0 1 1 1
5 1
0 1 1 1
0 1 2 1
0 3 3 1
1 4 1
1 3 1
Sample Output
0
0
2
3
2
0
Comments