zoj 3686 A Simple Tree Problem

题意就是给你一颗树。初始时每个节点的值都为0，现在有两种操作，‘o’操作是将以节点i为根的子树的每个节点取反，即0变1，1变0.‘q’操作是求以节点i为根的子树中1的个数。

方法主要是给每个节点分配一个区间，是这个区间的节点都是它的子节点。然后就是线段树的经典操作啦。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 #define lson l,m,rt<<1
  6 #define rson m+1,r,rt<<1|1
  7 #define maxn 100005
  8 struct node{
  9     int num,c;
 10 }setree[maxn<<2];
 11 struct{
 12     int y,next;
 13 }ee[maxn<<1];
 14 struct op{
 15     int l,r;
 16 }mes[maxn];
 17 int t,link[maxn],cnt;
 18 void insert(int a,int b)
 19 {
 20     ee[++t].y=b;
 21     ee[t].next=link[a];
 22     link[a]=t;
 23 }
 24 void dfs(int root,int father)
 25 {
 26     int tmp=cnt;
 27     mes[root].l=cnt;
 28     for(int i=link[root];i;i=ee[i].next){
 29         if(ee[i].y!=father){
 30             dfs(ee[i].y,root);
 31         }
 32     }
 33     if(tmp==cnt){
 34         mes[root].r=cnt++;
 35         return;
 36     }
 37     mes[root].r=cnt++;
 38 }
 39 void build(int l,int r,int rt)
 40 {
 41     setree[rt].num=0;
 42     setree[rt].c=0;
 43     if(l==r)
 44     return;
 45     int m=(l+r)>>1;
 46     build(lson);
 47     build(rson);
 48 }
 49 void pushdown(int rt,int len)
 50 {
 51     if(setree[rt].c){
 52         setree[rt<<1].c=1-setree[rt<<1].c;
 53         setree[rt<<1].num=len-len/2-setree[rt<<1].num;
 54         setree[rt<<1|1].c=1-setree[rt<<1|1].c;
 55         setree[rt<<1|1].num=len/2-setree[rt<<1|1].num;
 56         setree[rt].c=0;
 57     }
 58 }
 59 void pushup(int rt)
 60 {
 61     setree[rt].num=setree[rt<<1].num+setree[rt<<1|1].num;
 62 }
 63 void update(int l,int r,int rt,int L,int R)
 64 {
 65     if(L<=l&&r<=R){
 66         setree[rt].c=1-setree[rt].c;
 67         setree[rt].num=r-l+1-setree[rt].num;
 68         return;
 69     }
 70     int m=(l+r)>>1;
 71     pushdown(rt,r-l+1);
 72     if(L<=m)
 73     update(lson,L,R);
 74     if(R>m)
 75     update(rson,L,R);
 76     pushup(rt);
 77 }
 78 int query(int l,int r,int rt,int L,int R)
 79 {
 80     if(L<=l&&r<=R)
 81     return setree[rt].num;
 82     int m=(l+r)>>1;
 83     pushdown(rt,r-l+1);
 84     int ans=0;
 85     if(L<=m)
 86     ans+=query(lson,L,R);
 87     if(R>m)
 88     ans+=query(rson,L,R);
 89     return ans;
 90 }
 91 int main()
 92 {
 93     int n,m;
 94     while(~scanf("%d%d",&n,&m)){
 95         memset(link,0,sizeof(link));
 96         t=0;
 97         for(int i=2;i<=n;i++){
 98             int a;
 99             scanf("%d",&a);
100             insert(a,i);
101             insert(i,a);
102         }
103         cnt=1;
104         dfs(1,1);
105         build(1,n,1);
106         while(m--){
107             char s[5];
108             int a;
109             scanf("%s%d",s,&a);
110             if(s[0]=='o')
111             update(1,n,1,mes[a].l,mes[a].r);
112             else
113             printf("%d\n",query(1,n,1,mes[a].l,mes[a].r));
114         }
115         printf("\n");
116     }
117     return 0;
118 }

AC Code