题目大意：有一颗苹果树，开始时每个节点都有一个苹果，有两种操作，一种是问当前节点和它所有的子节点的苹果的个数和，第二个是改变当前节点的苹果数（0到1，1到0）
思路：刚开始直接用题目中给的树进行乱搞，果断TLE，，因为当树退化成链的时候就完蛋了
然后求一部分区间的和当然可以用线段树（本身就是一个树），但是这道题中的树不能直接用线段树，因为不只是叶子节点可以改变（虽然线段树乱搞下应该也可以），而且不是一个满二叉树（应该是这个名字吧。。），所以先进行个dfs，，建立一个映射的关系，搜索每个节点的时候都可以记录开始和结束的时间，结束的时候当前节点的子节点肯定都搜索一遍了，所以根据这两个时间就可以在映射之后求整个子树的和~
看不懂请看：
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<vector>using namespace std;const int maxn = 100100;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1struct Side{int u,v,next;}side[maxn];int top;int node[maxn];void add_side(int u,int v){side[top].u = u;side[top].v = v;side[top].next = node[u];node[u] = top ++;}int time[maxn][2];int t;void dfs(int now){t ++;time[now][0] = t;for(int i = node[now];i != -1;i = side[i].next){dfs(side[i].v);}time[now][1] = t;}///xian duan shuint sum[maxn<<2];void pushup(int rt){sum[rt] = sum[rt<<1] + sum[rt<<1|1];}void update(int x,int l,int r,int rt){if(l == r){sum[rt] = !sum[rt];return;}int m = (l + r)>>1;if(x <= m)update(x,lson);else update(x,rson);pushup(rt);}void build(int l,int r,int rt){if(l == r){sum[rt] = 1;return ;}int m = (l + r)>>1;build(lson);build(rson);pushup(rt);}int query(int L,int R,int l,int r,int rt){if(L <= l&&r <= R){return sum[rt];}int m = (l + r)>>1;int ans = 0;if(L <= m)ans += query(L,R,lson);if(R > m)ans += query(L,R,rson);return ans;}int main(){int n;while(~scanf("%d",&n)){if(n == 0)break;top = 0;memset(node,-1,sizeof(node));for(int i = 0;i < n-1;i ++){int a,b;scanf("%d%d",&a,&b);add_side(a,b);}memset(time,0,sizeof(time));t = 0;dfs(1);//for(int i = 1;i <= n;i ++){//cout<<time[i][0]<<' '<<time[i][1]<<endl;//}build(1,n,1);int m;scanf("%d",&m);while(m –){char op[4];int x;scanf("%s%d",op,&x);if(op[0] == 'Q'){printf("%d\n",query(time[x][0],time[x][1],1,n,1));}else if(op[0] == 'C'){update(time[x][0],1,n,1);}}}return 0;}
坚韧是成功的一大要素，只要在门上敲得够久够大声，终会把人唤醒的。
