Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3686
A Simple Tree Problem

Time Limit: 3 Seconds      Memory Limit: 65536 KB

Given a rooted tree, each node has a boolean (0 or 1) labeled on it. Initially, all the labels are 0.

We define this kind of operation: given a subtree, negate all its labels.

And we want to query the numbers of 1's of a subtree.


Multiple test cases.

First line, two integer N and M, denoting the numbers of nodes and numbers of operations and queries.(1<=N<=100000, 1<=M<=10000)

Then a line with N-1 integers, denoting the parent of node 2..N. Root is node 1.

Then M lines, each line are in the format "o node" or "q node", denoting we want to operate or query on the subtree with root of a certain node.


For each query, output an integer in a line.

Output a blank line after each test case.

Sample Input

3 2
1 1
o 2
q 1

Sample Output


Author: CUI, Tianyi
Contest: ZOJ Monthly, March 2013
Submit    Status