POJ3321深度优先搜索+树状数组

题意

传送门 POJ 3321

题解

求树的 $dfs$ 序&＃xff0c;每棵子树 $dfs$ 开始与结束的时间戳对应的区间&＃xff0c;用 $BIT$ 维护其苹果数量。一开始 $vector<int>G[MAX\_N]$ 存图 $TLE$&＃xff0c;逛了逛 $discuss$ &＃xff0c;没想到 $vector<vector<int>>G$ 才能过。

#include
#include
#include
#include
#include
#include
#include
#define min(a,b) (((a) <(b)) ? (a) : (b))
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define abs(x) ((x) <0 ? -(x) : (x))
#define INF 0x3f3f3f3f
#define delta 0.85
using namespace std;#define MAX_N 100005
int bit[MAX_N &＃43; 1], n;void add(int i, int x){while(i <&＃61; n){bit[i] &＃43;&＃61; x;i &＃43;&＃61; i & -i;}
}int sum(int i){int s &＃61; 0;while(i > 0){s &＃43;&＃61; bit[i];i -&＃61; i & -i;}return s;
}int N, M, V, clk;
vector<vector<int>> G;
int L[MAX_N], R[MAX_N], apple[MAX_N];void dfs(int v, int f){&＃43;&＃43;clk;L[v] &＃61; clk;for(int i &＃61; 0; i < G[v].size(); i&＃43;&＃43;){int u &＃61; G[v][i];if(u !&＃61; f) dfs(u, v);}R[v] &＃61; clk;
}void solve(){clk &＃61; 0;dfs(1, 0);n &＃61; N;for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){add(i, 1);apple[i] &＃61; 1;}for(int i &＃61; 0; i < M; i&＃43;&＃43;){char op;int x;scanf(" %c%d", &op, &x);if(op &＃61;&＃61; &＃39;C&＃39;){if(apple[x] & 1) add(L[x], -1);else add(L[x], 1);apple[x] ^&＃61; 1;}else{printf("%d\n", sum(R[x]) - sum(L[x] - 1));}}
}int main(){while(~scanf("%d", &N)){V &＃61; N;G &＃61; vector<vector<int>> (N &＃43; 1, vector<int>());for(int i &＃61; 0; i < N - 1; i&＃43;&＃43;){int u, v;scanf("%d%d", &u, &v);G[u].push_back(v); G[v].push_back(u);}scanf("%d", &M);solve();}return 0;
}