18754번 - Bitset Master 다국어

It’s well known in China that O(n²) algorithms can pass in a problem with n = 10⁶ easily.

You are given a tree with n vertices and n − 1 edges (u₁, v₁),(u₂, v₂), . . . ,(u_n−1, v_n−1). For each vertex u, there is a set S_u. Initially S_u = {u}.

There are two types of operations:

• “1 u”: output the number of sets S_v (1 ≤ v ≤ n) that contain u.
• “2 p”: take the sets S_up and S_vp and assign S_up ∪ S_vp to both of them.

You need to perform m operations. Output the answer for each operation of the first kind.

The first line contains two integers n, m (2 ≤ n ≤ 2 · 10⁵, 1 ≤ m ≤ 6 · 10⁵).

Each of the following n − 1 lines contains two integers u_i, v_i describing an edge of the tree (1 ≤ u_i, v_i ≤ n).

Each of the following m lines contains two integers t, w describing an operation (1 ≤ t ≤ 2, 1 ≤ w ≤ n + 1 − t).

For each operation of the first kind, output an integer on a separate line.