POJ - 3321 Apple Tree

题目链接：https://vjudge.net/problem/POJ-3321#author=mfdy

题目

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

现在的问题是不断会有新的苹果长出来,卡卡也随时可能摘掉一个苹果吃掉。你能帮助卡卡吗? 输入数据：第一行包含一个整数N（N <= 100000）,表示树上节点的数目。 接下来N-1行，每行包含2个整数u和v，表示u和v是连在一起的。 下一行包含一个整数M（M ≤ 100,000）. 接下来M行包含下列两种命令之一： "C x" 表示某个节点上的苹果发生了变化，如果原来没有苹果，则现在长出了一个苹果；如果原来有苹果，则是卡卡把它吃了。 "Q x" 表示查询x节点上的子树上的苹果有多少。包含节点x.

思路

因为树上的节点编号并不是连续的，所以可以使用DFS序将树节点进行重新编号。low[u]表示u的dfs序，high[u]表示以u为根节点的子树最后一个dfs序号。所以以u为根节点的树，其节点编号是low[u]~high[u]，就变成了一段连续的编号。u子树的苹果数量 = query(high[u]) - query(low[u]-1).
其low[u]和high[u]如图所示

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5+10;
using namespace std;

int N,Q;
int h[maxn],e[maxn*2],ne[maxn*2],idx;
int tr[maxn],app[maxn];
int low[maxn],high[maxn];
void add(int a,int b){
    e[++idx] = b,ne[idx] = h[a],h[a] = idx; 
}
int lowbit(int x){
    return x&-x;
}
void add(int idx){
    int v;
    if(app[idx] == 1) v = -1,app[idx] = 0;
    else v = 1,app[idx] = 1;
    for(int i = idx;i<=N;i += lowbit(i)) tr[i] += v;
}
int query(int r){
    int sum = 0;
    for(int i = r;i>=1;i -= lowbit(i)) sum += tr[i];
    return sum;
}
int tim = 0;
void DFS(int u,int fa = -1){
    low[u] = ++tim;
    for(int i = h[u]; i; i = ne[i]){
        int v = e[i];
        if(v == fa) continue;
        DFS(v,u);
    }
    high[u] = tim;
}

int main(){
    ios;
    cin>>N;
    for(int i = 1;i<=N-1;i++){
        int a,b;cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    DFS(1);
    for(int i = 1;i<=N;i++) add(low[i]);
    cin>>Q;
    string op;int t;
    while(Q--){
        cin>>op>>t;
        if(op == "Q") cout<<query(high[t]) - query(low[t]-1)<<'\n';
        else add(low[t]);
    }
    return 0;
}