題目鏈接：http://poj.org/problem?id=3321

解題思路：

先dfs求出序列，將子樹轉化到dfs序列的區間內，接下來就是簡單的樹狀數組求和模型了。水題。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 100005; struct Edge {int to,next; }edge[maxn<<1]; struct Tree {int n,c[maxn];void init(int n){this->n = n;memset(c,0,sizeof(c));}int lowbit(int x){return x & -x;}void update(int x,int d){while(x <= n){c[x] += d;x += lowbit(x);}}int sum(int x){int ans = 0;while(x > 0){ans += c[x];x -= lowbit(x);}return ans;} }tree; int n,cnt,head[maxn]; int L[maxn],R[maxn],tot;void addedge(int u,int v) {edge[cnt].to = v;edge[cnt].next = head[u];head[u] = cnt++; }void dfs(int u,int fa) {L[u] = ++tot;for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if(v == fa) continue;dfs(v,u);}R[u] = tot; }int main() {int u,v;char op[2];while(scanf("%d",&n)!=EOF){cnt = tot = 0;memset(head,-1,sizeof(head));for(int i = 1; i < n; i++){scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}dfs(1,-1);tree.init(tot);for(int i = 1; i <= tot; i++)tree.update(i,1);int q;scanf("%d",&q);while(q--){scanf("%s",op);scanf("%d",&u);if(op[0] == 'Q')printf("%d\n",tree.sum(R[u]) - tree.sum(L[u]-1));else{int tmp = tree.sum(L[u]) - tree.sum(L[u]-1);if(tmp == 0) tmp = 1;else tmp = -1;tree.update(L[u],tmp);}}}return 0; }

總結

以上是生活随笔為你收集整理的poj 3321 Apple Tree(dfs序+树状数组求和模型)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。