poj 3321 Apple Tree

思路：将树形结构转为线性结构，用线段树统计苹果数。包含了线段树的两个基本操作。单点更新区间查询。通过这道题掌握了将树形结构转为线性结构的方法。
AC Code
  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{
  9     int l,r,num;
 10 }mes[maxn];
 11 struct{
 12     int y,next;
 13 }ee[maxn<<1];
 14 int setree[maxn<<2];
 15 int link[maxn],t,cnt;
 16 void insert(int a,int b)
 17 {
 18     ee[++t].y=b;
 19     ee[t].next=link[a];
 20     link[a]=t;
 21 }
 22 void dfs(int root,int father)
 23 {
 24     int tmp=cnt;
 25     mes[root].l=100000;
 26     for(int i=link[root];i;i=ee[i].next)
 27     if(ee[i].y!=father){
 28         dfs(ee[i].y,root);
 29         mes[root].l=min(mes[root].l,mes[ee[i].y].l);
 30     }
 31     mes[root].r=cnt;
 32     if(tmp==cnt){
 33         mes[root].l=cnt;
 34         mes[root].num=cnt++;
 35         return;
 36     }
 37     mes[root].num=cnt++;
 38 }
 39 void build(int l,int r,int rt)
 40 {
 41     setree[rt]=r-l+1;
 42     if(l==r)
 43     return;
 44     int m=(l+r)>>1;
 45     build(lson);
 46     build(rson);
 47 }
 48 void update(int l,int r,int rt,int pos)
 49 {
 50     if(l==r){
 51         setree[rt]=1-setree[rt];
 52         return;
 53     }
 54     int m=(l+r)>>1;
 55     if(pos<=m)
 56     update(lson,pos);
 57     else
 58     update(rson,pos);
 59     setree[rt]=setree[rt<<1]+setree[rt<<1|1];
 60 }
 61 int query(int l,int r,int rt,int L,int R)
 62 {
 63     if(L<=l&&r<=R)
 64     return setree[rt];
 65     int m=(l+r)>>1;
 66     int ans=0;
 67     if(L<=m)
 68     ans+=query(lson,L,R);
 69     if(R>m)
 70     ans+=query(rson,L,R);
 71     return ans;
 72 }
 73 int main()
 74 {
 75     int n;
 76     while(~scanf("%d",&n)){
 77         t=0;
 78         cnt=1;
 79         memset(link,0,sizeof(link));
 80         for(int i=1;i<n;i++){
 81             int a,b;
 82             scanf("%d%d",&a,&b);
 83             insert(a,b);
 84             insert(b,a);
 85         }
 86         dfs(1,1);
 87         build(1,n,1);
 88         int m;
 89         scanf("%d",&m);
 90         while(m--){
 91             char s[5];
 92             int op;
 93             scanf("%s%d",s,&op);
 94             if(s[0]=='Q')
 95             printf("%d\n",query(1,n,1,mes[op].l,mes[op].r));
 96             else
 97             update(1,n,1,mes[op].num);
 98         }
 99     }
100     return 0;
101 }