CODEVS.1228 苹果树(DFS序)

Description

在卡卡的房子外面，有一棵苹果树。每年的春天，树上总会结出很多的苹果。卡卡非常喜欢吃苹果，所以他一直都精心的呵护这棵苹果树。我们知道树是有很多分叉点的，苹果会长在枝条的分叉点上面，且不会有两个苹果结在一起。卡卡很想知道一个分叉点所代表的子树上所结的苹果的数目，以便研究苹果树哪些枝条的结果能力比较强。

卡卡所知道的是，每隔一些时间，某些分叉点上会结出一些苹果，但是卡卡所不知道的是，总会有一些调皮的小孩来树上摘走一些苹果。

于是我们定义两种操作：

C x	表示编号为x的分叉点的状态被改变(原来有苹果的话，就被摘掉，原来没有的话，就结出一个苹果)
G x	查询编号为x的分叉点所代表的子树中有多少个苹果

我们假定一开始的时候，树上全都是苹果，也包括作为根结点的分叉1。

Input Description

第一行一个数N (n<=100000)

接下来n-1行,每行2个数u,v,表示分叉点u和分叉点v是直接相连的。

再接下来一行一个数M,(M<=100000)表示询问数

接下来M行,表示询问,询问的格式如题目所述Q x或者C x

Output Description

对于每个Q x的询问,请输出相应的结果,每行输出一个

Sample Input

1 2

1 3

Q 1

C 2

Q 1

Sample Output

思路：

　　DFS序+线段树。

代码：

 1 #include<cstdio>
 2 using namespace std;
 3 const int N=100005;
 4 
 5 int n,Enum,cnt,H[N<<1],Dfn[N],Size[N],Sum[N<<2];
 6 struct Edge
 7 {
 8     int to,nxt;
 9 }e[N<<1];
10 
11 int read()
12 {
13     int now=0;char c=getchar();
14     while(c>'9'||c<'0')c=getchar();
15     while(c>='0'&&c<='9')now=(now<<3)+(now<<1)+c-'0',c=getchar();
16     return now;
17 }
18 
19 void AddEdge(int u,int v)
20 {
21     e[++Enum].to = v;
22     e[Enum].nxt = H[u];
23     H[u] = Enum;
24 }
25 
26 void dfs(int x,int fa)
27 {
28     Dfn[x]=++cnt;
29 //    Size[x]=1;
30     for(int i=H[x];i;i=e[i].nxt)
31       if(e[i].to!=fa)
32       {
33           dfs(e[i].to,x);
34 //            Size[x]+=Size[e[i].to];
35             Size[x]+=Size[e[i].to]+1;
36       }
37 }
38 
39 void PushUp(int rt)
40 {
41     Sum[rt]= Sum[rt<<1]+Sum[rt<<1|1];
42 }
43 
44 void Build(int l,int r,int rt)
45 {
46     if(l==r)
47     {
48         Sum[rt]=1;
49         return;
50     }
51     int m=(l+r)>>1;
52     Build(l,m,rt<<1);
53     Build(m+1,r,rt<<1|1);
54     PushUp(rt);
55 }
56 
57 void XorPoint(int l,int r,int rt,int pos)
58 {
59     if(l==r)
60     {
61         Sum[rt]^=1;
62         return;
63     }
64     int m=(l+r)>>1;
65     if(pos<=m) XorPoint(l,m,rt<<1,pos);
66     else XorPoint(m+1,r,rt<<1|1,pos);
67     PushUp(rt);
68 }
69 
70 int QuerySum(int l,int r,int rt,int L,int R)
71 {
72     if(L<=l && r<=R) return Sum[rt];
73     int m=(l+r)>>1,ans=0;
74     if(L<=m) ans+=QuerySum(l,m,rt<<1,L,R);
75     if(m<R) ans+=QuerySum(m+1,r,rt<<1|1,L,R);
76     return ans;
77 }
78 
79 int main()
80 {
81     n=read();
82     Build(1,n,1);
83     for(int u,v,i=1;i<n;i++)
84       u=read(),v=read(),AddEdge(u,v),AddEdge(v,u);
85     dfs(1,-1);
86 //    for(int i=1;i<=n;i++)
87 //      printf("%d:dfn:%d  size:%d
",i,Dfn[i],Size[i]);
88     int m=read();char opt[5];int x;
89     while(m--)
90     {
91         scanf("%s",opt);x=read();
92         if(opt[0]=='Q')
93 //          printf("%d
",QuerySum(1,n,1,Dfn[x],Dfn[x]+Size[x]-1));
94           printf("%d
",QuerySum(1,n,1,Dfn[x],Dfn[x]+Size[x]));
95         else
96           XorPoint(1,n,1,Dfn[x]);
97     }
98     return 0;
99 }