DMOPC '20 Contest 7 P4 - Mimi and Carrots II

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Everything changed. At that terrible moment. We knew that home was a tree with N nodes, and carrots were food.

The Land of the Carrot Trees was once a peaceful land, with N cities connected with N-1 roads. This all changed one day, when Mimi the carrot-loving cat invaded, and forced the Carrot King into exile!

The Carrot King is constantly on the run. Every day, for the next Q days, one of two types of events happens:

  1. His spies tell him that city u_j has either become a safe haven where he can hide, or if it was safe, that it has been completely overrun. Initially, no city is safe.
  2. He asks how safe it is to travel from city u_j to city v_j. This value is equal to the number of distinct safe cities c_j such that c_j is either on the path from u_j to v_j, or there exists a city d_j such that d_j is on the path from u_j to v_j, and there exists an edge between c_j and d_j.

As the royal adviser, it is up to you to implement a program that answers the king's queries. Can you save the king?


1 \le N, Q \le 2 \times 10^5

Subtask 1 [10%]

1 \leq N, Q \leq 2 \times 10^3

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line of input contains 2 space-separated integers N and Q.

The next N-1 lines each contain 2 space-separated integers a_i and b_i, indicating there is an edge from a_i to b_i.

The next Q lines first contain an integer t_j \in \{1, 2\}, indicating the type of the event:

  • If t_j = 1, then a single integer u_j (1 \le u_j \le N) follows.
  • If t_j = 2, then 2 integers u_j and v_j (1 \le u_j, v_j \le N) follow.

Output Specification

For each type 2 event, output the answer on a new line.

Sample Input

6 5
1 2
1 3
2 4
4 6
2 5
1 4
2 2 3
2 4 2
1 4
2 5 3

Sample Output



  • 4
    justin_g_20  commented on June 21, 2021, 4:15 a.m.

    wait… where’ sub task 2? I can only see 1 and 3

    • 3
      Kirito  commented on June 21, 2021, 10:49 a.m.

      Riolku killed it with fire.