dfs 线段树   poj3321

#include<cstdio>
#include<vector>
using namespace std;
const int maxn=1e5+10;
pair<int,int> pa[maxn];
int head[maxn],cnt=0;
struct EDGE { int next,to; } edge[maxn];
void ADD(int u,int v){
    edge[++cnt].next=head[u];
    edge[cnt].to=v;
    head[u]=cnt;
}
int tot=0;
void dfs(int x,int fa){
    pa[x].first=++tot;
    for(int i=head[x];i!=0;i=edge[i].next){
        int u=edge[i].to;
        if(u==fa) continue;
        dfs(u,x);
    }
    pa[x].second=tot;
}
struct NODE { int l,r,w; }tree[4*maxn+10];
void build(int p,int q,int k){
    tree[k].l=p;  tree[k].r=q;
    if(tree[k].l==tree[k].r)  { tree[k].w=1; return ; }
    int mid=( tree[k].l+tree[k].r )/2;
    build(p,mid,2*k);  build(mid+1,q,2*k+1);
    tree[k].w=tree[2*k].w+tree[2*k+1].w;
}
void change_interval(int a,int b,int x,int k) // 区间修改  区间加值；
{
    if(tree[k].l>=a && tree[k].r<=b ){
        if(tree[k].w==1) tree[k].w=0;
        else             tree[k].w=1;
        return;
    }
    int mid=(tree[k].l+tree[k].r)/2;
    if(b<=mid)         change_interval(a,b,x,2*k);
    else if(a>=mid+1)  change_interval(a,b,x,2*k+1);
    else               change_interval(a,mid,x,2*k),change_interval(mid+1,b,x,2*k+1);
    tree[k].w=tree[k*2].w+tree[k*2+1].w;
}
int ask_interval(int a,int b,int k)  // 区间查询
{
    int num=0;
    if(tree[k].l>=a&&tree[k].r<=b){
        num=tree[k].w;
        return num;
    }
    int mid=( tree[k].l+tree[k].r)/2;
    if(b<=mid)        num+=ask_interval(a,b,2*k);
    else if(a>=mid+1) num+=ask_interval(a,b,2*k+1);
    else              num+=ask_interval(a,mid,2*k)+ask_interval(mid+1,b,2*k+1);
    return num;
}
char ch[2];
int c;
int main(){
    int n; scanf("%d",&n);
    for(int i=1;i<=n-1;i++){
        int  x,y; scanf("%d %d",&x,&y);ADD(x,y);
    }
    dfs(1,1);
    build(1,n,1);
    int q; scanf("%d",&q);
    while(q--){
        scanf("%s %d",ch,&c);
        if(ch[0]=='Q') {
            printf("%d\n",ask_interval(pa[c].first,pa[c].second,1));
        }
        else {
           change_interval(pa[c].first,pa[c].first,1,1);
        }

    }
}

View Code