P3703 [SDOI2017] Tree Node Coloring

Bob has a rooted tree with $n$ nodes, where node $1$ is the root. Bob painted each node with a color, and all nodes have pairwise distinct colors. Define the weight of a path as the number of distinct colors among the nodes on this path (including both endpoints). Bob may perform the following operations: - `1 x` Recolor all nodes on the path from $x$ to the root with a brand-new color that has never been used before. - `2 x y` Query the weight of the path from $x$ to $y$. - `3 x` Within the subtree rooted at $x$, choose a node so that the weight of its path to the root is maximized; output that maximum weight. Bob will perform $m$ operations in total.

The first line contains two integers $n, m$. The next $n-1$ lines each contain two integers $a, b$, indicating an edge between $a$ and $b$. The next $m$ lines describe the operations, in the format given in the statement.

For each operation of type 2 or 3, output one line. For type 2, output one integer: the weight of the path. For type 3, output one integer: the maximum weight.

There are 10 test points. Test point 1: $1 \leq n, m \leq 1000$. Test points 2 and 3: no type 2 operations. Test points 4 and 5: no type 3 operations. Test point 6: the tree is generated as follows — for $i$ ($2 \leq i \leq n$), randomly choose a node from $1$ to $i-1$ as the parent of $i$. Test point 7: $1 \leq n, m \leq 5 \times 10^4$. Test point 8: $1 \leq n \leq 5 \times 10^4$. Test points 9 and 10: no special restrictions. For all testdata: $1 \leq n \leq 10^5$, $1 \leq m \leq 10^5$. Translated by ChatGPT 5