| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 125 | 44 | 22 | 26.506% |
There is a tree with $n$ vertices. An edge of the tree may be either a light edge or a heavy edge. You need to perform $m$ operations on the tree. Initially, all edges on the tree are light edges. There are two operations:
Given two vertices $a$ and $b,ドル for all $x$ on the path between $a$ and $b$ (including $a$ and $b$ themselves), you need to turn all edges connected with $x$ into light edges, and turn all edges on the path between $a$ and $b$ into heavy edges.
Given two vertices $a$ and $b,ドル you need to compute the number of heavy edges on the path between $a$ and $b$.
The first line is an integer $T$ denoting the number of test cases. For each test case, the first line has two integers $n$ and $m$ where $n$ is the number of vertices and $m$ is the number of operations.
For the next $n-1$ lines, each line contains two integers $u$ and $v$ denoting an edge of the tree.
For the next $m$ lines, each line contains three integers $op_i,a_i,b_i$ denoting an operation. $op_i = 1$ means the operation is an operation of the first type, while $op_i = 2$ means the operation is an operation of the second type.
It's guaranteed that $a_i \ne b_i$ in all operations.
For each operation of the second type, output an integer denoting the answer to the query.
For all test sets, $T \le 3,ドル 1ドル \le n,m \le 10^5$.
1 7 7 1 2 1 3 3 4 3 5 3 6 6 7 1 1 7 2 1 4 2 2 7 1 1 5 2 2 7 1 2 1 2 1 7
1 3 2 1
After operation 1, the heavy edges are $(1,3)$; $(3,6)$; $(6,7)$.
In operation 2, the only heavy edge on the path from vertex 1ドル$ to vertex 4ドル$ is $(1,3)$.
In operation 3, the heavy edges on the path from vertex 2ドル$ to vertex 7ドル$ are $(1,3)$; $(3,6)$; $(6,7)$.
After operation 4, $(1,3)$ and $(3,6)$ will become light edges first, and then $(1,3)$ and $(3,5)$ will become heavy edges.
In operation 5, the heavy edges on the path from vertex 2ドル$ to vertex 7ドル$ are $(1,3)$ and $(6,7)$.
After operation 6, edge $(1,3)$ will become a light edge while $(1,2)$ will become a heavy edge.
In operation 7, the heavy edge on the path from vertex 1ドル$ to vertex 7ドル$ is edge $(6,7)$.