POJ – 3321 Apple Tree dfs序+线段树 简单题

Apple Tree dfs序+线段树 简单题

Source

POJ - 3321

My Solution

题意：初始时树上每个节点都有1个苹果，然后对一个节点操作，如果有苹果，就拿走，没苹果，就放上，然后询问以x为根的子树上有多少个苹果。

dfs序+线段树 简单题

POJ这题好像没有开O2，vector sons[MAXN];一直TLE，换了邻接表就过了。

时间复杂度 O(n)

空间复杂度 O(4*n)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 8;

struct Edge{
    int v,next;
}edge[2*MAXN];
int head[MAXN];
int tot;
//dfs序
int p1[MAXN], p2[MAXN], ti = 0;
//int dfsnum[MAXN];  //这个按情况是否需要。
void init(){
    memset(head, -1, sizeof head);
    tot = 0; ti = 0;
}

void add_edge(int a,int b){
    edge[tot] = (Edge){b, head[a]};
    head[a] = tot++;
}

void dfs(int u, int fa){
    p1[u] = ++ti;
    int i, v;
    for(i = head[u]; i != -1; i = edge[i].next){
        v = edge[i].v;
        if(v == fa) continue;
        dfs(v, u);
    }
    p2[u] = ti;
}
//线段树
int sum[4*MAXN];
int size;
inline void pushup(int Ind){
    sum[Ind] = sum[Ind<<1] + sum[(Ind<<1) + 1];
}

inline int _Query(int a, int b, int l, int r, int Ind){
    if(a <= l && b >= r) return sum[Ind];
    int mid = (l+r)>>1; int ret = 0;
    if(a <= mid) ret += _Query(a, b, l, mid, Ind<<1); if(b > mid) ret += _Query(a, b, mid + 1, r, (Ind<<1) + 1); return ret; } inline void _Modify(int a, int l, int r, int Ind){ if(l == r && l == a){ sum[Ind] ^= 1; return; } int mid = (l+r)>>1;
    if(a <= mid) _Modify(a, l, mid, Ind<<1);
    else _Modify(a, mid + 1, r, (Ind<<1) + 1); pushup(Ind); } inline void _build(int l, int r, int Ind){ if(l == r){ sum[Ind] = 1; return; } int mid = (l+r)>>1;
    _build(l, mid, Ind<<1);
    _build(mid + 1, r, (Ind<<1) + 1);
    pushup(Ind);
}

inline int Query(int a, int b) {return _Query(a, b, 1, size, 1);}
inline void Modify(int a){return _Modify(a, 1, size, 1);}


int main()
{
    #ifdef LOCAL
    freopen("b.txt", "r", stdin);
    //freopen("b.out", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    int n, m, i, u, v, x, root;
    char ch[6];
    scanf("%d", &n);
    init();
    for(i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    dfs(1, -1);

    scanf("%d", &m);

    size = ti;
    _build(1, size, 1);
    while(m--){
        scanf("%s%d", ch, &x);
        if(ch[0] == 'C'){
            Modify(p1[x]);
        }
        else{
            printf("%dn", Query(p1[x], p2[x]));
        }
    }


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx