POJ - 3321 Apple Tree （dfs序+线段树）

识字粗堪供赋役，不须辛苦慕公卿。这篇文章主要讲述POJ - 3321 Apple Tree （dfs序+线段树）相关的知识，希望能为你提供帮助。
【POJ - 3321 Apple Tree （dfs序+线段树）】题目链接：http://poj.org/problem?id=3321
题目大意：给定一棵树，某些节点上有苹果，多次询问各子树上的节点数，并且在询问的中途随时可能新增和删除苹果。
Sample Input

3 1 2 1 3 3 Q 1 C 2 Q 1

Sample Output

3 2

emmm，刚开始的时候还以为是个树剖呢，板子都打好了。。。它要的是整个子树，所以我们利用dfs序将整个树化为一个序列，然后跑线段树就行了，跑dfs的时候记录一下进入时间戳和出去的时间戳。
以下是AC代码：

#include < cstdio> #include < algorithm> #include < cstring> #include < iostream> using namespace std; #define lson l,mid,rt< < 1 #define rson mid+1,r,rt< < 1|1 #define lc rt< < 1 #define rc rt< < 1|1 const int mac=1e5+10; struct Edge { int to,next; }eg[mac< < 1]; int num=0,head[mac],in[mac],out[mac],id; int tree[mac< < 2]; void add(int u,int v) { eg[num].to=v; eg[num].next=head[u]; head[u]=num++; }void dfs(int x,int fa) { in[x]=++id; for (int i=head[x]; i!=-1; i=eg[i].next){ int v=eg[i].to; if (v==fa) continue; dfs(v,x); } out[x]=id; }void build(int l,int r,int rt) { if (l==r) {tree[rt]=1; return; } int mid=(l+r)> > 1; build(lson); build(rson); tree[rt]=tree[lc]+tree[rc]; }void update(int l,int r,int rt,int pos) { if (l==r) {tree[rt]^=1; return; } int mid=(l+r)> > 1; if (mid> =pos) update(lson,pos); else {update(rson,pos); } tree[rt]=tree[lc]+tree[rc]; }int query(int l,int r,int rt,int L,int R) { int ans=0; if (l> =L & & r< =R) return tree[rt]; int mid=(l+r)> > 1; if (mid> =L) ans+=query(lson,L,R); if (mid< R) ans+=query(rson,L,R); return ans; }int main(int argc, char const *argv[]) { int n,q; scanf ("%d",& n); memset(head,-1,sizeof head); for (int i=1; i< =n-1; i++){ int u,v; scanf ("%d%d",& u,& v); add(u,v); add(v,u); } scanf ("%d",& q); dfs(1,0); build(1,n,1); for (int i=1; i< =q; i++){ char s[5]; int x; scanf ("%s%d",s,& x); if (s[0]==‘Q‘) printf("%d ",query(1,n,1,in[x],out[x])); else update(1,n,1,in[x]); } return 0; }