Codeforces Round 200 (Div. 1) |
---|
Закончено |
Безумный ученый Майк построил корневое дерево, которое состоит из n вершин. Каждая вершина представляет собой резервуар, который может быть либо пуст, либо заполнен водой.
Вершины дерева пронумерованы числами от 1 до n. Корень дерева находится в вершине 1. Резервуары детей каждой вершины расположены ниже резервуара этой вершины, при этом вершина соединена с каждым из детей трубой, по которой вниз может стекать вода.
Майк хочет выполнять с деревом следующие операции:
Изначально все вершины дерева пусты.
Майк уже составил полный список операций, которые он хочет выполнить по порядку. Перед испытанием дерева Майк решил провести симуляцию этих действий. Помогите Майку определить, какие результаты он получит в результате выполнения всех операций.
В первой строке входных данных записано целое число n (1 ≤ n ≤ 500000) — количество вершин в дереве. В каждой из следующих n - 1 строк через пробел записаны по два целых числа ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — ребра дерева.
В следующей строке дано целое число q (1 ≤ q ≤ 500000) — количество операций. В каждой из следующих q строк через пробел записано по два целых числа ci (1 ≤ ci ≤ 3), vi (1 ≤ vi ≤ n), где ci обозначает номер типа операции (согласно нумерации в условии), а vi обозначает вершину, над которой проводится операция.
Гарантируется, что данный граф является деревом.
Для каждой операции типа 3 выведите на отдельной строке 1, если вершина заполнена, и 0, если вершина пуста. Ответы на запросы выводите в том порядке, в котором запросы даны во входных данных.
5
1 2
5 1
2 3
4 2
12
1 1
2 3
3 1
3 2
3 3
3 4
1 2
2 4
3 1
3 3
3 4
3 5
0
0
0
1
0
1
0
1
Название |
---|