P7735 [NOI2021] Light and Heavy Edges

Xiao W has a tree with $n$ nodes. Each edge in the tree can be either a light edge or a heavy edge. Next, you need to perform $m$ operations on the tree. Before all operations start, all edges in the tree are light edges. There are two types of operations: 1. Given two nodes $a$ and $b$, first, for every node $x$ on the path from $a$ to $b$ (including $a$ and $b$), you must change all edges incident to $x$ into light edges. Then, change all edges on the path from $a$ to $b$ into heavy edges. 2. Given two nodes $a$ and $b$, you need to compute how many heavy edges are currently on the path from $a$ to $b$.

This problem has multiple test cases. The first line of the input contains a positive integer $T$, which indicates the number of test cases. For each test case: The first line contains two integers $n$ and $m$, where $n$ is the number of nodes and $m$ is the number of operations. The next $n - 1$ lines each contain two integers $u\ v$, representing an edge in the tree. The next $m$ lines each contain three integers ${\mathit{op}}_i\ a_i\ b_i$, describing an operation, where ${\mathit{op}}_i = 1$ denotes an operation of type 1, and ${\mathit{op}}_i = 2$ denotes an operation of type 2. The data guarantees that $a_i \neq b_i$.

For each operation of type 2, output one line containing one integer, which is the answer.

**[Sample Explanation #1]** After the 1st operation, the heavy edges are: $(1, 3)$, $(3, 6)$, $(6, 7)$. In the 2nd operation, the heavy edges on the path are: $(1, 3)$. In the 3rd operation, the heavy edges on the path are: $(1, 3)$, $(3, 6)$, $(6, 7)$. In the 4th operation, first $(1, 3)$ and $(3, 6)$ become light edges, and then $(1, 3)$ and $(3, 5)$ become heavy edges. In the 5th operation, the heavy edges on the path are: $(1, 3)$, $(6, 7)$. In the 6th operation, first $(1, 3)$ becomes a light edge, and then $(1, 2)$ becomes a heavy edge. In the 7th operation, the heavy edges on the path are: $(6, 7)$. **[Sample #2]** See the attachments `edge/edge2.in` and `edge/edge2.ans`. The constraints of this sample are consistent with test points $3 \sim 6$. **[Sample #3]** See the attachments `edge/edge3.in` and `edge/edge3.ans`. The constraints of this sample are consistent with test points $9 \sim 10$. **[Sample #4]** See the attachments `edge/edge4.in` and `edge/edge4.ans`. The constraints of this sample are consistent with test points $11 \sim 14$. **[Sample #5]** See the attachments `edge/edge5.in` and `edge/edge5.ans`. The constraints of this sample are consistent with test points $17 \sim 20$. **[Constraints]** For all testdata: $T \le 3$, $1 \le n, m \le {10}^5$. | Test Point ID | $n, m \le $ | Special Property | |:-:|:-:|:-:| | $1 \sim 2$ | $10$ | None | | $3 \sim 6$ | $5000$ | None | | $7 \sim 8$ | ${10}^5$ | A, B | | $9 \sim 10$ | ${10}^5$ | A | | $11 \sim 14$ | ${10}^5$ | B | | $15 \sim 16$ | $2\times {10}^4$ | None | | $17 \sim 20$ | ${10}^5$ | None | Special property A: The tree is a chain. Special property B: In each type 2 operation, $a_i$ and $b_i$ are directly connected by an edge. Translated by ChatGPT 5