poj 3321 Apple Trie

/*poj 3321 Apple Trie 這道題的關鍵是如何將一個樹建成一個一維數組利用樹狀數組來解題！可以利用dfs（）來搞定，我們在對一個節點深搜后，所經過的節點的數目就是該節點的子樹的數目所以我們利用start[i]數組來記錄 i 節點在一維數組的起始位置， 而end[i]則是記錄i節點所有孩子 節點最后一個孩子節點在數組的位置，那么end[i]-start[i]+1，就是 i 節點（包括自身）和其所有孩子節點的數目。數組建好了，那么最后就是套用樹狀數組模板進行求解了！ 
*/
#include<iostream> 
#include<vector>
#include<cstring>
#include<cstdio>
#define N 100005
using namespace std;
class node
{
public :int k;node *next;node(){next=NULL;}
};node trie[N];
//trie[i]記錄的是所有是 i 節點 孩子節點組成的鏈表的頭部 
int C[N], num[N];
int start[N], end[N];
int cnt, n;void dfs(int cur)
{start[cur]=cnt;if(trie[cur].next==NULL){end[cur]=cnt;return;}for(node *p=trie[cur].next; p!=NULL; p=p->next)//遍歷cur節點的所有孩子節點 {++cnt;dfs(p->k);}end[cur]=cnt;//深搜之后得到的cnt值就是cur節點最后一個孩子在一維數組中的位置 
}int lowbit(int x)
{return x&(-x);
}void init(int p, int k)
{int i;num[p]=k;for(i=p-lowbit(p)+1; i<=p; ++i)C[p]+=num[i];
}int getSum(int p)
{int s=0;	while(p>0){s+=C[p];p-=lowbit(p);}return s;
}void update(int p, int k)
{while(p<=n){C[p]+=k;p+=lowbit(p);}
}int main()
{int i, u, v, m;char ch[2];int f;while(scanf("%d", &n)!=EOF){cnt=1;memset(C, 0, sizeof(C));for(i=1; i<n; ++i){scanf("%d%d", &u, &v);node *p=new node();p->k=v;p->next=trie[u].next;trie[u].next=p;}dfs(1);for(i=1; i<=n; ++i)init(i, 1);scanf("%d", &m);while(m--){scanf("%s%d", ch, &f);if(ch[0]=='C'){if(num[f]==1){update(start[f], -1);num[f]=0;}else{update(start[f], 1);num[f]=1;} }elseprintf("%d\n", getSum(end[f])-getSum(start[f]-1));}}return 0;
}

/*
   這道題利用二維數組建圖也可以過，不過數組的大小還真是難以捉摸....
*/
#include<iostream> 
#include<vector>
#include<cstring>
#include<cstdio>
#define N 100005
using namespace std;
int node[N][100];
int C[N], num[N];
int start[N], end[N];
int cnt, n;void dfs(int cur)
{int sz=node[cur][0];start[cur]=cnt;if(sz==0){end[cur]=cnt;return;}for(int i=1; i<=sz; ++i){++cnt;dfs(node[cur][i]);}end[cur]=cnt;
}int lowbit(int x)
{return x&(-x);
}void init(int p, int k)
{int i;num[p]=k;for(i=p-lowbit(p)+1; i<=p; ++i)C[p]+=num[i];
}int getSum(int p)
{int s=0;	while(p>0){s+=C[p];p-=lowbit(p);}return s;
}void update(int p, int k)
{while(p<=n){C[p]+=k;p+=lowbit(p);}
}int main()
{int i, u, v, m;char ch[2];int f;while(scanf("%d", &n)!=EOF){cnt=1;for(i=1; i<=n; ++i)node[i][0]=0;memset(C, 0, sizeof(C));for(i=1; i<n; ++i){scanf("%d%d", &u, &v);node[u][++node[u][0]]=v;}dfs(1);for(i=1; i<=n; ++i)init(i, 1);scanf("%d", &m);while(m--){scanf("%s%d", ch, &f);if(ch[0]=='C'){if(num[f]==1){update(start[f], -1);num[f]=0;}else{update(start[f], 1);num[f]=1;} }elseprintf("%d\n", getSum(end[f])-getSum(start[f]-1));}}return 0;
}