POJ.3321 Apple Tree ( DFS序 线段树 单点更新 区间求和)

题意分析

卡卡屋前有一株苹果树，每年秋天，树上长了许多苹果。卡卡很喜欢苹果。树上有N个节点，卡卡给他们编号1到N，根的编号永远是1.每个节点上最多结一个苹果。卡卡想要了解某一个子树上一共结了多少苹果。

现在的问题是不断会有新的苹果长出来,卡卡也随时可能摘掉一个苹果吃掉。你能帮助卡卡吗?

前缀技能

边表存储树

DFS时间戳

线段树

首先利用边表将树存储下来，然后DFS打上时间戳。打上时间戳之后，我们就知道书上节点对应维护线段树的哪一段区间了。换句话说，每当题目给出一个点，要求更新的时候，我们根据时间戳，确定其点在线段树上的位置。当题目给出一个区间，要求我们查询的时候，再根据时间戳，确定线段树区间左右端点。如此一来，就可以将树上信息，转换到线段树上来维护。

注意

1. 值得注意的是，我的边表存的是两条边，所以边表的容量要开二倍。
2. 其次就是，无论在更新的时候，还是在查询的时候，要根据时间戳，转化到线段树的对应点或者区间上。因为这个WA了。

代码总览

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#define nmax 100010

using namespace std;

struct edge{

    int to,next;

}edg[nmax<<1];

struct Tree{

    int l,r,val;

    int mid(){

        return (l+r)>>1;

    }

};

Tree tree[nmax<<2];

int head[nmax],in[nmax],out[nmax];

int tot = 0,n,m,time = 0;

void add(int u, int v){

    edg[tot].to = v;

    edg[tot].next = head[u];

    head[u] = tot++;

}

void init(){

    memset(head,-1,sizeof head);

    memset(edg, 0, sizeof edg);

    memset(tree,0,sizeof tree);

    memset(in,0,sizeof in);

    memset(out ,0, sizeof out);

    tot= 0;

    time = 0;

}

void dfs(int rt,int f){

    time++;

    in[rt] = time;

    for(int i = head[rt]; i!= -1;i= edg[i].next){

        int net = edg[i].to;

        if(net != f) dfs(net,rt);

    }

    out[rt] = time;

}

void PushUp(int rt)

{

    tree[rt].val = tree[rt<<1].val + tree[rt<<1|1].val;

}

void Build(int l, int r, int rt)

{

    tree[rt].l = l; tree[rt].r = r;

    if(l == r){

        tree[rt].val = 1;

        return;

    }

    Build(l,tree[rt].mid(),rt<<1);

    Build(tree[rt].mid()+1,r,rt<<1|1);

    PushUp(rt);

}

void UpdatePoint(int pos, int rt)

{

    if(tree[rt].l == tree[rt].r){

        tree[rt].val ^= 1;

        return;

    }

    if(pos<= tree[rt].mid()) UpdatePoint(pos,rt<<1);

    else UpdatePoint(pos,rt<<1|1);

    PushUp(rt);

}

int Query(int l,int r,int rt)

{

    if(l>tree[rt].r || r<tree[rt].l) return 0;

    if(l <= tree[rt].l && tree[rt].r <= r) return tree[rt].val;

    return Query(l,r,rt<<1) + Query(l,r,rt<<1|1);

}

int main()

{

    while(scanf("%d",&n) != EOF){

        init();

        int u,v;

        for(int i = 0;i<n-1;++i){

            scanf("%d %d",&u,&v);

            add(u,v);

            add(v,u);

        }

        dfs(1,0);

        Build(1,n,1);

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

        char op;int x;

        for(int i = 0;i<m;++i){

            scanf(" %c %d",&op,&x);

            if(op == 'Q'){

                printf("%d\n",Query(in[x],out[x],1));

            }else{

                UpdatePoint(in[x],1);

            }

        }

    }

    return 0;

}