
ZOJ Problem Set  3686
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. Input 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 N1 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. Output 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 1 Author: CUI, Tianyi Contest: ZOJ Monthly, March 2013 