Waterloo 2023 Winter E - Colourful Tree

View as PDF

Submit solution

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

Problem types

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 1 with colour C on the tree. Then there are q operations of two types coming in order:

  • 0 x c d: Add a new vertex indexed n+1 with colour c to the tree, where n is the current number of existing vertices. An edge connecting vertex x and (n+1) with length d will also be added to the tree.
  • 1 x c: Change the colour of vertex x to c.
  • After each operation, you should find a pair of vertices u and v (1u,vn) with different colours in the current tree so that the distance between u and v is as large as possible.

The distance between two vertices u and v is the length of the shortest path from u to v on the tree.

Input Specification

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

The first line of the input contains two integers q and C (1q5×105,1Cq) indicating the number of operations and the initial colour of vertex 1.

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

  • If the i-th line contains 4 integers 0, xi, ci and di (1xin,1ciq,1d109), the i-th operation will add a new vertex n+1 with colour ci to the tree and connect it to vertex xi with an edge of length di.
  • If the i-th line contains 3 integers 1, xi and ci (1xin,1ciq), the i-th operation will change the colour of vertex xi to ci.
  • It's guaranteed that the sum of q of all test cases will not exceed 5×105.

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

Copy
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

Copy
0
0
2
3
2
0

Comments

There are no comments at the moment.