Булево дерево
시간 제한2초메모리 제한256 MB
트리의 한 정점에 변수 값 대입이 추가될 때마다, 가장 가까운 조상의 최신 대입을 물려받는 규칙 아래에서 해당 변수가 참, 거짓, 미정의인 리프의 수를 각각 출력한다.
문제
Виталик очень долго думал как решить простенькую задачку, и в процессе придумывания решения нарисовал на доске граф. Этот граф по стечению обстоятельств оказался корневым деревом. В этот момент к доске подошел Боря, и начал записывать в некоторых вершинах дерева выражения, в которых булевым переменным присваивались различные значения.
После этого они ввели правило, по которому для каждой вершины дерева можно определить значение переменной в этой вершине. А именно, если в этой вершине записывалось присваивание этой переменной значения, то используется последнее такое значение. Если таким образом значение определить не удалось, то берется значение этой переменной в ближайшем предке этой вершины, в котором записано присваивание значение этой переменной. Если у вершины нет такого предка, значит значение не определено.
После нескольких операций они захотели посчитать для заданной переменной в скольких листьях дерева значение этой переменной true, в скольких false, а в скольких не определено. И тут они поняли, что это сложно, и что сделать этого они не могут. Поэтому они просят вас помочь им, и после каждого добавления записи о присваивании значения переменной, определять, для скольких листьев значение этой переменной равно true, для скольких false, а для скольких не определено.
입력
В первой строке задано число T — число тестов. Далее идёт описание T тестов.
В первой строке теста даны два натуральных числа n и m (1 ≤ n, m ≤ 105), где n – количество вершин заданного дерева, а m – количество добавлений новых записей о присваивании значения переменной. Во второй строке даны n чисел, где i-е число это номер предка i-й вершины. Для корня это число равно нулю. Гарантируется, что вам дано именно дерево. Далее идут m строк – описания записей. В каждой из этих строк содержатся три числа: v – номер вершины, x – номер переменной и b – ноль либо единица, если значение переменной равно false или true соответственно. Номер переменной – это целое положительное число, не превосходящее 105.
В каждом наборе входных данных сумма всех n и сумма всех m не превышают 105.
출력
Для каждого из тестовых примеров выводите m строк, содержащие по три числа – количество листьев дерева, для которых значение только что написанной переменной равно true, false и не определено, соответственно.