#P18483. Jumping Lights
Jumping Lights
Jumping Lights
给你一棵树,即一张有 个顶点、 条边的无向连通图。最开始,没有任何顶点被标记。你需要处理 次下列三种操作:
0 w:取消顶点 的标记。如果它原本没有被标记,则什么也不做。1 w:标记顶点 。如果它原本已经被标记,则什么也不做。2:同时对树中的所有顶点进行以下更新:如果该顶点有至少一个已被标记的邻点,则将该顶点标记;否则取消该顶点的标记。
第三种操作的所有判断都使用操作前的标记状态。顶点不把自己当作邻点;它原先被标记,并不能单独保证更新后仍被标记。
每次操作后,求树中已被标记的顶点数量。
输入格式
第一行包含两个整数 (,),分别表示顶点数和操作数。
接下来 行,每行两个整数 (),表示树的一条边。
接下来 行,每行按照上面的格式描述一次操作。对于前两种操作,。
输出格式
输出一行,包含 个整数,第 个整数表示第 次操作后已被标记的顶点数量。
原样例 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
4 5
1 2
1 3
2 4
1 2
2
0 4
2
2
1 2 1 2 2