Apple Tree （dfs序+线段树）

 1 /*dfs+线段树（单点修改+区间查询）*/
 2 #include "iostream"
 3 #include "vector"
 4 #include "map"
 5 #include "cstdio"
 6 #include "cstring"
 7 
 8 using namespace std;
 9 typedef long long ll;
10 const int maxn = 100005;
11 int n,m,_time,cnt;
12 int num[maxn],in[maxn],out[maxn],last[maxn];
13 int sum[maxn<<2];
14 struct data{
15     int to,_next;
16 }e[maxn<<1];
17 
18 void add(int u,int v){
19     e[++cnt].to = v; e[cnt]._next=last[u]; last[u]=cnt;
20     e[++cnt].to = u; e[cnt]._next=last[v]; last[v]=cnt;
21 }
22 
23 void dfs_arr(int x,int fa){
24     in[x]=++_time;
25     num[_time]=x;
26     for(int i=last[x];i;i=e[i]._next){
27         if( e[i].to!=fa ) dfs_arr(e[i].to,x);
28     }
29     out[x]=_time;
30 }
31 
32 void build(int pt,int l,int r){
33     int mid=(l+r)>>1;
34     if( l==r ){
35         sum[pt]=1;
36         return ;
37     }
38     build(pt<<1,l,mid);
39     build(pt<<1|1,mid+1,r);
40     sum[pt] = sum[pt<<1]+sum[pt<<1|1];
41 }
42 
43 int query(int pt,int L,int R, int l,int r){
44     if( L<=l&&R>=r ) return sum[pt];
45     int mid=(l+r)>>1;
46 
47     int sum=0;
48     if( L<=mid ) sum+=query(pt<<1,L,R,l,mid);
49     if( R>mid ) sum+=query(pt<<1|1,L,R,mid+1,r);
50     return sum;
51 }
52 
53 void modify(int pt,int x,int l,int r)
54 {
55     int mid=(l+r)>>1;
56     if( l==r )
57     {
58         sum[pt]^=1;
59         return ;
60     }
61     if( x<=mid ) modify(pt<<1,x,l,mid);
62     else modify(pt<<1|1,x,mid+1,r);
63     sum[pt] = sum[pt<<1]+sum[pt<<1|1];
64     return ;
65 }
66 
67 
68 int main()
69 {
70     scanf("%d",&n);
71     for(int i=1;i<n;i++ ){
72         int u,v;
73         scanf("%d%d",&u,&v);
74         add(u,v);
75     }
76     dfs_arr(1,0);
77     scanf("%d",&m);
78     char ch[10];
79     build(1,1,n);
80     for(int i=1;i<=m;i++){
81         scanf("%s",ch+1);
82         int x;
83         scanf("%d",&x);
84         if( ch[1]=='Q' ) printf("%d
",query(1,in[x],out[x],1,n));
85         else modify(1,in[x],1,n);
86     }
87     return 0;
88 }