NOI '21 P1 - Light Heavy Edges

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type

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:

  1. 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.

  2. Given two vertices a and b, you need to compute the number of heavy edges on the path between a and b.

Input Specification

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.

Output Specification

For each operation of the second type, output an integer denoting the answer to the query.

Sample Input 1

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

Sample Output 1

1
3
2
1

Explanation for Sample Output 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).

Additional Samples

Sample inputs and outputs can be found here.

  • Sample 2 (edge2.in and edge2.ans) corresponds to cases 3-6.
  • Sample 3 (edge3.in and edge3.ans) corresponds to cases 9-10.
  • Sample 4 (edge4.in and edge4.ans) corresponds to cases 11-14.
  • Sample 5 (edge5.in and edge5.ans) corresponds to cases 17-20.

Constraints

For all test sets, T \le 3, 1 \le n,m \le 10^5.

Test Case n,m \le Additional Constraints
1~2 10 None.
3~6 5000
7~8 10^5 A,B
9~10 A
11~14 B
15~16 2 \times 10^4 None.
17~20 10^5

Constraint A means the tree is a path.
Constraint B means for operations of the second type, a_i and b_i are directly connected by an edge.


Comments

There are no comments at the moment.