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.

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 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.

Output

For each query, output an integer in a line.

Output a blank line after each test case.

Sample Input

3 21 1o 2q 1

Sample Output

1

---

Author: CUI, Tianyi

Contest: ZOJ Monthly, March 2013

 

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5   6 #define lson l,m,rt<<1  7 #define rson m+1,r,rt<<1|1  8   9 using namespace std; 10  11 vector
         
           g[200010]; 12 int n,m,id; 13  14 const int maxn=200010; 15  16 struct Interval 17 { 18     int from,to; 19 }I[200010]; 20  21 void dfs(int node) 22 { 23     I[node].from=id; 24     id++; 25     int t=g[node].size(); 26     for(int i=0;i
          
           >1; 60 push_down(rt); 61 build(lson); build(rson); 62 push_up(rt); 63 } 64 65 void update(int L,int R,int l,int r,int rt) 66 { 67 if(L<=l&&r<=R) 68 { 69 xxo[rt]^=1; 70 swap(m0[rt],m1[rt]); 71 return ; 72 } 73 int m=(l+r)>>1; 74 push_down(rt); 75 if(L<=m) update(L,R,lson); 76 if(R>m) update(L,R,rson); 77 push_up(rt); 78 } 79 80 int query(int L,int R,int l,int r,int rt) 81 { 82 if(L<=l&&r<=R) 83 { 84 push_down(rt); 85 return m1[rt]; 86 } 87 int m=(l+r)>>1,ret=0; 88 push_down(rt); 89 if(L<=m) ret+=query(L,R,lson); 90 if(R>m) ret+=query(L,R,rson); 91 push_up(rt); 92 return ret; 93 } 94 95 int main() 96 { 97 while(scanf("%d%d",&n,&m)!=EOF) 98 { 99 for(int i=0;i<=n+10;i++) g[i].clear();100 memset(m0,0,sizeof(m0));101 memset(m1,0,sizeof(m1));102 memset(xxo,0,sizeof(xxo));103 for(int i=2;i<=n;i++)104 {105 int a;106 scanf("%d",&a);107 g[a].push_back(i);108 }109 id=1;110 dfs(1);111 build(1,n,1);112 while(m--)113 {114 char cmd[5]; int a;115 scanf("%s%d",cmd,&a);116 if(cmd[0]=='o') update(I[a].from,I[a].to,1,n,1);117 else if(cmd[0]=='q') printf("%d\n",query(I[a].from,I[a].to,1,n,1));118 }119 putchar(10);120 }121 return 0;122 }