Jumping Lights

시간 제한3초메모리 제한2048 MB

요약
처음에는 모든 정점이 표시되지 않은 트리에서 정점을 표시하거나 해제하는 질의와, 모든 정점을 이웃에 표시된 정점이 있는지에 따라 동시에 갱신하는 질의를 처리하며 각 질의 후 표시된 정점 수를 구한다.
난이도

어려움10점 중 8점

유형
트리, 시뮬레이션, 구현, 수학
정답자
아직 제출이 없습니다

문제

You are given a tree: an undirected connected graph on nn vertices with n−1n-1 edges. Initially, none of the vertices are marked. Your task is to process qq queries of the following three types:

  • "0 ww": unmark vertex ww; if ww is not marked, nothing happens.
  • "1 ww": mark vertex ww; if ww is marked, nothing happens.
  • "2": simultaneously for all vertices in the tree: mark the vertex if it has at least one marked neighbor, otherwise unmark it.

After each query, find how many marked vertices are there in the tree.

입력

The first line contains two integers nn and qq (2≤n≤3⋅1052 \le n \le 3 \cdot 10^5; 1≤q≤1061 \le q \le 10^6): the number of vertices in the tree and the number of queries, respectively.

Each of the next n−1n-1 lines describes an edge of the tree by two integers uu and vv (1≤u,v≤n1 \le u, v \le n).

Each of the next qq lines represents a query in the format shown above (1≤w≤n1 \le w \le n).

출력

Print a single line with qq integers: the number of marked vertices in the tree after each query.

예제2

  1. 예제 1

    입력
    8 8
1 2
2 3
2 4
1 5
5 6
5 7
5 8
1 1
2
2
0 1
0 3
0 4
0 5
2
    예상 출력
    1 2 6 5 4 3 3 1

  2. 예제 2

    입력
    4 5
1 2
1 3
2 4
1 2
2
0 4
2
2
    예상 출력
    1 2 1 2 2