#P9665. [ICPC2021 Macao R] Colorful Tree
[ICPC2021 Macao R] Colorful Tree
题目描述
Your task is to maintain a colorful tree and process queries.
At the beginning, there is only one vertex numbered with color on the tree. Then there are operations of two types coming in order:
- : Add a new vertex indexed with color 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.
- : Change the color of vertex to .
After each operation, you should find a pair of vertices and () with colors 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.
输入格式
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 color 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 color 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 color of vertex to .
It's guaranteed that the sum of of all test cases will not exceed .
输出格式
For each operation output the maximum distance between two vertices with different colors. If no valid pair exists output instead.
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
0
0
2
3
2
0