ZOJ 3686 A Simple Tree Problem

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

Sample Output

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

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <vector>
  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<int> 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<t;i++)
 27     {
 28         dfs(g[node][i]);
 29     }
 30     I[node].to=id-1;
 31 }
 32 
 33 int m0[maxn<<2],m1[maxn<<2],xxo[maxn<<2];
 34 
 35 void push_up(int rt)
 36 {
 37     m0[rt]=m0[rt<<1]+m0[rt<<1|1];
 38     m1[rt]=m1[rt<<1]+m1[rt<<1|1];
 39 }
 40 
 41 void push_down(int rt)
 42 {
 43     if(xxo[rt])
 44     {
 45         xxo[rt<<1]^=1; xxo[rt<<1|1]^=1;
 46         swap(m0[rt<<1|1],m1[rt<<1|1]);swap(m0[rt<<1],m1[rt<<1]);
 47         xxo[rt]=0;
 48     }
 49 }
 50 
 51 void build(int l,int r,int rt)
 52 {
 53     xxo[rt]=0;m0[rt]=0;m1[rt]=0;
 54     if(l==r)
 55     {
 56         m0[rt]=1; m1[rt]=0;
 57         return ;
 58     }
 59     int m=(l+r)>>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
",query(I[a].from,I[a].to,1,n,1));
118         }
119         putchar(10);
120     }
121     return 0;
122 }