22085번 - Булево дерево 다국어

Виталик очень долго думал как решить простенькую задачку, и в процессе придумывания решения нарисовал на доске граф. Этот граф по стечению обстоятельств оказался корневым деревом. В этот момент к доске подошел Боря, и начал записывать в некоторых вершинах дерева выражения, в которых булевым переменным присваивались различные значения.

После этого они ввели правило, по которому для каждой вершины дерева можно определить значение переменной в этой вершине. А именно, если в этой вершине записывалось присваивание этой переменной значения, то используется последнее такое значение. Если таким образом значение определить не удалось, то берется значение этой переменной в ближайшем предке этой вершины, в котором записано присваивание значение этой переменной. Если у вершины нет такого предка, значит значение не определено.

После нескольких операций они захотели посчитать для заданной переменной в скольких листьях дерева значение этой переменной true, в скольких false, а в скольких не определено. И тут они поняли, что это сложно, и что сделать этого они не могут. Поэтому они просят вас помочь им, и после каждого добавления записи о присваивании значения переменной, определять, для скольких листьев значение этой переменной равно true, для скольких false, а для скольких не определено.

В первой строке задано число T — число тестов. Далее идёт описание T тестов.

В первой строке теста даны два натуральных числа n и m (1 ≤ n, m ≤ 10⁵), где n – количество вершин заданного дерева, а m – количество добавлений новых записей о присваивании значения переменной. Во второй строке даны n чисел, где i-е число это номер предка i-й вершины. Для корня это число равно нулю. Гарантируется, что вам дано именно дерево. Далее идут m строк – описания записей. В каждой из этих строк содержатся три числа: v – номер вершины, x – номер переменной и b – ноль либо единица, если значение переменной равно false или true соответственно. Номер переменной – это целое положительное число, не превосходящее 10⁵.

В каждом наборе входных данных сумма всех n и сумма всех m не превышают 10⁵.

Для каждого из тестовых примеров выводите m строк, содержащие по три числа – количество листьев дерева, для которых значение только что написанной переменной равно true, false и не определено, соответственно.