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 (1 \le u, v \le n) 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 (1 \le q \le 5 \times 10^5, 1 \le C \le q) 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, x_i, c_i and d_i (1 \le x_i \le n, 1 \le c_i \le q, 1 \le d \le 10^9), the i-th operation will add a new vertex n+1 with colour c_i to the tree and connect it to vertex x_i with an edge of length d_i.
  • If the i-th line contains 3 integers 1, x_i and c_i (1 \le x_i \le n, 1 \le c_i \le q), the i-th operation will change the colour of vertex x_i to c_i.
  • It's guaranteed that the sum of q of all test cases will not exceed 5 \times 10^5.

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

There are no comments at the moment.