题目:美丽的中国结

题目描述

题目背景
kitty刚刚高三毕业.看到同学们都回家的回家,旅游的旅游,她的心里有些落寞.英俊潇洒风流倜傥迷倒万千KL却仅对kitty感冒的fish看在眼里,急在心里.一天,fish提出和kitty两个人一起外出旅游.kitty犹豫了几天,想好能瞒过家长的理由后（要问是什么……自己猜去）,答应了.fish很高兴地带着kitty去登记了（别想歪,登记旅游团而已……）,日照青岛五日游.
当然啦,他们玩得很高兴.虽然这次旅行是fish先提议的,但kitty因为玩得很畅快（刚高考完嘛）,所以想送给fish一份礼物,一份能让见多识广的fish都无法忘怀的礼物.她从路边 9¾站台的某算命先生那里得知中国结具有增加RP的效果,而这正是fish所需要的,因此她决定动手给fish编一个奇特的中国结.

题目描述
中国结形式多样,fish会喜欢什么样的呢?思考几天后,kitty决定给fish编一个树状的中国结.这个中国结有n个结点（编号1,2,…,n）,这n个结点之间总共恰有n-1条线相连,其中结点1上是树的根.这是一个奇特的中国结,因此它的编织方式也很奇特.在编织过程中的每一步骤,kitty有时需要将一个结点子树里的所有结点i的状态全部取反（如果原来结点i已经打结,则解开i,否则将结点i打结）,有时又需要知道一个结点的子树里有多少已经打结的结点,你能帮助可爱的kitty完成这份礼物吗?

数据规模
对于40% 的数据,1≤n≤10000, 1≤m≤20000
对于100%的数据,1≤n≤100000, 1≤m≤100000

输入格式

输入
第一行有个整数n,表示这个中国结有n个结点
以下n-1行,每行有两个整数u和v(1≤u,v≤n),表示结点u和v间有一条线相连；
再一行有个整数m,表示kitty要进行的步骤数
以下m行,每行可能为:
"C x":表示将结点x的子树中所有结点的状态取反（包括x）
或
"Q x":表示kitty想知道结点x的子树中有多少已经打结的结点（包括x）

输出格式

对于每个“Q x”输出一行整数,表示结点x的子树中有多少已经打结的结点（包括x）

原来scanf输入字符时换行符也当成字符。

做的第一道线段树的题目，死缠烂打了一天，突然发现只是 l 打成了 r,悲剧啊。

暂时还没领会到线段树的优越性。加油啊！！！！！！

  1 #include<iostream>
  2 #include<stdio.h>
  3 #define Max 200010
  4 using namespace std;
  5 
  6 int n,m;
  7 int num=0,ans=0;
  8 
  9 int edg[Max],edgs=0;
 10 int first[Max]={0},next[Max]={0},last[Max]={0};
 11 bool v[Max]={0};
 12 int sl[Max],sr[Max];  //记录每个节点儿孙们的范围，包括自己 
 13 bool mark[Max]={0};
 14 int sum[Max]={0};
 15 int now=1,lson[Max],rson[Max],lbig[Max],rbig[Max];  //son[]记录线段的儿子   big[]记录自己的大小 
 16 
 17 void Make_edg(int x,int y){
 18      edgs++;
 19      edg[edgs]=y;
 20      if(first[x]==0)
 21      {first[x]=edgs;last[x]=edgs;}
 22      else {next[last[x]]=edgs;last[x]=edgs;}
 23      }
 24 void Dfs(int node){
 25      v[node]=1;
 26      ++num;
 27      sl[node]=num;
 28      for(int i=first[node];i>0;i=next[i])
 29      if(!v[edg[i]])
 30      {Dfs(edg[i]);}
 31      sr[node]=num;
 32      }
 33 void Make_tree(int l,int r){
 34      lbig[now]=l;rbig[now]=r;
 35      if(l==r) return ;
 36      int mid=(l+r)>>1;
 37      int temp=now;
 38      lson[temp]=++now;
 39      Make_tree(l,mid);
 40      rson[temp]=++now;
 41      Make_tree(mid+1,r);
 42      }
 43 void Init(){
 44      scanf("%d",&n);
 45      for(int i=1;i<n;++i)
 46      {
 47        int x,y;
 48        scanf("%d%d",&x,&y);
 49        Make_edg(x,y);
 50        Make_edg(y,x);
 51              }
 52      Dfs(1);
 53      Make_tree(1,num);
 54      }
 55 
 56 
 57 void change(int l,int r,int now){
 58      if(lbig[now]==l&&rbig[now]==r)
 59      {
 60        if(mark[now]) mark[now]=0;
 61        else mark[now]=1;
 62        sum[now]=rbig[now]-lbig[now]+1-sum[now];
 63        return ;
 64                                             }
 65      if(mark[now])
 66      {
 67        if(mark[lson[now]]) mark[lson[now]]=0;
 68        else mark[lson[now]]=1;
 69        sum[lson[now]]=rbig[lson[now]]-lbig[lson[now]]+1-sum[lson[now]];
 70        if(mark[rson[now]]) mark[rson[now]]=0;
 71        else mark[rson[now]]=1;
 72        sum[rson[now]]=rbig[rson[now]]-lbig[rson[now]]+1-sum[rson[now]];
 73        mark[now]=0;
 74                   }
 75      
 76      int mid=(rbig[now]+lbig[now])>>1;
 77      if(mid>=r) change(l,r,lson[now]);
 78      else if(mid<l) change(l,r,rson[now]);
 79      else {change(l,mid,lson[now]);change(mid+1,r,rson[now]);}
 80     
 81      sum[now]=sum[lson[now]]+sum[rson[now]];
 82      }
 83 
 84 void Question(int l,int r,int now){
 85      if(lbig[now]==l&&rbig[now]==r)  {ans+=sum[now];return ;}
 86      
 87      if(mark[now])
 88      {
 89        if(mark[lson[now]]) mark[lson[now]]=0;
 90        else mark[lson[now]]=1;
 91        sum[lson[now]]=rbig[lson[now]]-lbig[lson[now]]+1-sum[lson[now]];
 92        if(mark[rson[now]]) mark[rson[now]]=0;
 93        else mark[rson[now]]=1;
 94        sum[rson[now]]=rbig[rson[now]]-lbig[rson[now]]+1-sum[rson[now]];
 95        mark[now]=0;
 96                   }
 97      
 98      int mid=(rbig[now]+lbig[now])>>1;
 99      if(mid>=r) Question(l,r,lson[now]);
100      else if(mid<l) Question(l,r,rson[now]);
101      else {Question(l,mid,lson[now]);Question(mid+1,r,rson[now]);}
102      }
103 
104 void Work(){
105      scanf("%d",&m);
106      char s;int x;
107      scanf("%c",&s);
108      for(int i=1;i<=m;++i)
109      {
110        scanf("%c%d",&s,&x);
111        if(s=='C')
112        change(sl[x],sr[x],1);
113        if(s=='Q')
114        {
115          ans=0;
116          Question(sl[x],sr[x],1);
117          printf("%d\n",ans);       
118                  }
119        scanf("%c",&s);
120              }
121      }
122 
123 int main()
124 {
125     Init();
126     Work();
127     }