在卡卡的房子外面，有一棵苹果树。每年的春天，树上总会结出很多的苹果。卡卡非常喜欢吃苹果，所以他一直都精心的呵护这棵苹果树。我们知道树是有很多分叉点的，苹果会长在枝条的分叉点上面，且不会有两个苹果结在一起。卡卡很想知道一个分叉点所代表的子树上所结的苹果的数目，以便研究苹果树哪些枝条的结果能力比较强。
卡卡所知道的是，每隔一些时间，某些分叉点上会结出一些苹果，但是卡卡所不知道的是，总会有一些调皮的小孩来树上摘走一些苹果。
于是我们定义两种操作：
C x | 表示编号为x的分叉点的状态被改变(原来有苹果的话，就被摘掉，原来没有的话，就结出一个苹果) |
G x | 查询编号为x的分叉点所代表的子树中有多少个苹果 |
我们假定一开始的时候，树上全都是苹果，也包括作为根结点的分叉1。
第一行一个数N (n<=100000)
接下来n-1行,每行2个数u,v,表示分叉点u和分叉点v是直接相连的。
再接下来一行一个数M,(M<=100000)表示询问数
接下来M行,表示询问,询问的格式如题目所述Q x或者C x
对于每个Q x的询问,请输出相应的结果,每行输出一个
3
1 2
1 3
3
Q 1
C 2
Q 1
3
2
分析 Analysis
首先这道题理论基础：DFS序（树操）+ 线段树
好在那个长苹果不是每秒，不然我就ctrl+w了qwq
首先读进来后撸成DFS序为基础的线性结构
那么根据DFS序，这道题可以化归为：树上单点修改 + 求子树和
如果到这里还没看懂请补全DFS序的理论部分qwq（然后怎么做超显然的）
-------------------------------------------------------------------------
我第一次拿到这道题的时候，还真不知道怎么写
好在CZL夏令营的时候帮我补了树操
orzCZL
代码 Code
1 #include<cstdio> 2 #include<iostream> 3 #define mid (L+R)/2 4 #define lc (rt<<1) 5 #define rc (rt<<1|1) 6 #define maxn 1000000 7 using namespace std; 8 9 int dfn[maxn],TIM = 1,dfn_t[maxn],n,a,b,c,m,pos,tl[maxn]; 10 char ctr; 11 12 struct edge{ 13 int from,v; 14 }e[maxn]; 15 16 struct node{ 17 int sum; 18 }Tree[maxn]; 19 20 void maintain(int rt){ 21 Tree[rt].sum = Tree[lc].sum+Tree[rc].sum; 22 } 23 24 void build(int rt,int L,int R){ 25 if(L == R) Tree[rt].sum = 1; 26 else{ 27 build(lc,L,mid); 28 build(rc,mid+1,R); 29 30 maintain(rt); 31 } 32 } 33 34 void add(int rt,int L,int R,int pos){ 35 if(L == R) Tree[rt].sum ^= 1; 36 else{ 37 if(pos <= mid) add(lc,L,mid,pos); 38 else add(rc,mid+1,R,pos); 39 40 maintain(rt); 41 } 42 } 43 44 int query(int rt,int L,int R,int qL,int qR){ 45 if(qL <= L && R <= qR) return Tree[rt].sum; 46 else{ 47 int ans = 0; 48 if(qL <= mid) ans += query(lc,L,mid,qL,qR); 49 if(qR > mid) ans += query(rc,mid+1,R,qL,qR); 50 return ans; 51 } 52 } 53 54 void PRINT(int rt,int L,int R){ 55 if(L == R) printf("%d ",Tree[rt].sum); 56 else{ 57 PRINT(lc,L,mid); 58 PRINT(rc,mid+1,R); 59 } 60 } 61 62 int tot,first[maxn]; 63 void insert(int u,int v){ 64 tot++; 65 e[tot].from = first[u]; 66 e[tot].v = v; 67 first[u] = tot; 68 } 69 70 void dfs(int now,int pre){ 71 dfn[now] = TIM++; 72 tl[dfn[now]] = now; 73 // Tree[dfn[now]].sum = 1; 74 for(int i = first[now];i;i = e[i].from){ 75 int v = e[i].v; 76 if(v != pre){ 77 dfs(v,now); 78 } 79 }dfn_t[now] = TIM++; 80 tl[dfn_t[now]] = now; 81 } 82 83 int main(){ 84 scanf("%d",&n); 85 for(int i = 1;i < n;i++){ 86 scanf("%d%d",&a,&b); 87 insert(a,b); 88 insert(b,a); 89 } 90 91 92 dfs(1,-1); 93 TIM--; 94 // build(1,1,TIM-1); 95 for(int i = 1;i <= n;i++){ 96 add(1,1,TIM,dfn[i]); 97 } 98 99 scanf("%d",&m);100 for(int i = 1;i <= m;i++){101 cin >> ctr >> pos;102 if(ctr == ‘C‘) add(1,1,TIM,dfn[pos]);103 else printf("%d\n",query(1,1,TIM,dfn[pos],dfn_t[pos]));104 // PRINT(1,1,TIM-1);cout << endl;105 }106 107 // for(int i = 1;i <= n;i++){108 // printf("%d ",dfn[i]);109 // }cout << "##";110 111 // for(int i = 1;i <= TIM;i++) printf("%d ",tl[i]);112 113 return 0;114 }
情绪低落= =
