C++-POJ3321-Apple Tree[数据结构][树状数组]

树上的单点修改+子树查询

用dfn[u]和num[u]可以把任意子树表示成一段连续区间，此时结合树状数组就好了

#include <set>

#include <map>

#include <cmath>

#include <queue>

#include <vector>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int MAXN=(int)1e5+;

const int MAXM=(int)2e5+;

int a[MAXN],n,m;char s[];

int lb(int i){return i&-i;}//lowbit

void add(int i,int v){for(;i<=n;a[i]+=v,i+=lb(i));}

int sum(int i){int ans=;for(;i;ans+=a[i],i-=lb(i));return ans;}

int query(int i,int j){return sum(j)-sum(i-);}

struct node{int v,next;}edge[MAXM];

int head[MAXN],cnt;

void addedge(int u,int v){edge[++cnt].v=v,edge[cnt].next=head[u],head[u]=cnt;}

void Addedge(int u,int v){addedge(u,v),addedge(v,u);}

int dfn[MAXN],num[MAXN],index;

void dfs(int u,int fa){

    dfn[u]=++index;

    for(int i=head[u];i;i=edge[i].next){

        int v=edge[i].v;

        if(v!=fa)num[u]++,dfs(v,u),num[u]+=num[v];

    }

}

void Order_C(int x){query(dfn[x],dfn[x])?add(dfn[x],-):add(dfn[x],);}

void Order_Q(int x){printf("%d\n",query(dfn[x],dfn[x]+num[x]));}

int main() {

    scanf("%d",&n);

    for(int i=,u,v;i<n;i++)scanf("%d%d",&u,&v),Addedge(u,v);

    dfs(,),scanf("%d",&m);

    for(int i=;i<=n;i++)add(i,);

    for(int i=,x;i<=m;i++)scanf("%s%d",s,&x),s[]=='C'?Order_C(x):Order_Q(x);

    return ;

}