## Waterloo 2023 Winter E - Colourful Tree

View as PDF

Points: 25
Time limit: 6.0s
Memory limit: 512M

Problem types

2023 Winter Waterloo Local Contest, Problem E

At the beginning, there is only one vertex numbered with colour on the tree. Then there are operations of two types coming in order:

• 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 and is the length of the shortest path from to on the tree.

#### Input Specification

There are multiple test cases. The first line of the input contains an integer indicating the number of test cases. For each test case:

The first line of the input contains two integers and indicating the number of operations and the initial colour of vertex .

For the following lines, each line describes an operation taking place in order with or integers.

• 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