, Huang, Jinsong题目链接：?id=3321题目大意：有棵苹果树，开始每个结点都有一个苹果，C x表示该点有苹果则吃掉，没有则长出，Q x表示询问x结点上包括x结点的苹果数量题目分析：将苹果树倒过来形成一个树形结构，因为其后序遍历的结果是一段连续的区间，并且以x为根的子树根为区间的右端点，因此可以通过树状数组来求解此问题，，用DFS预处理出每个结点子树的左右区间。#include <cstdio>#include <cstring>int const MAX = 1e5 + 5;int head[MAX], c[MAX], a[MAX];int n, m, cnt, num;struct EDGE{int to, next;}e[MAX];struct NODE{int l, r;}nd[MAX];void Add(int x, int y){e[cnt].to = y;e[cnt].next = head[x];head[x] = cnt++;}void DFS(int now){nd[now].l = num;for(int i = head[now]; i != -1; i = e[i].next)DFS(e[i].to);nd[now].r = num ++;}int lowbit(int x){return x & (-x);}void change(int x){if(a[x]){for(int i = x; i < num; i += lowbit(i))c[i] ++;}else{for(int i = x; i < num; i += lowbit(i))c[i] –;}}int cal(int x){int res = 0;for(int i = x; i > 0; i -= lowbit(i))res += c[i];return res;}int main(){scanf("%d", &n);memset(head, -1, sizeof(head));memset(c, 0, sizeof(c));cnt = 0;for(int i = 0; i < n – 1; i++){int x, y;scanf("%d %d", &x, &y);Add(x, y);}num = 1;DFS(1);for(int i = 1; i <= n; i++){a[i] = 1;change(i);}scanf("%d", &m);while(m –){int x;char s[2];scanf("%s %d", s, &x);if(s[0] == 'Q')printf("%d\n", cal(nd[x].r) – cal(nd[x].l – 1));else{a[nd[x].r] = (a[nd[x].r] + 1) % 2;change(nd[x].r);}}}
爱情要完结的时候自会完结，到时候，你不想画上句号也不行。
