POJ 3321 Apple Tree - c++编程基础

] = ++cou;
int pre = cou;
visit[k] = true;
for(int i=pt[k]; i!=-1; i=b[i].next)
{
if(!visit[b[i].end])
{

dfs(b[i].end);
}
}
num[k] = cou - pre + 1;
}
int find(int x)
{
return x&(-x);
}
int get_sum(int x)
{
int s=0;
while(x>0)
{
s+=a[x];
x-=find(x);
}
return s;
}
void update(int x,int val)
{
while(x<=n)
{
a[x] += val;
x += find(x);
}
}

/***************************************************************
> File Name: POJ3321.cpp
> Author: SDUT_GYX
> Mail: 2272902662@qq.com
> Created Time: 2013/6/5 10:30:04
**************************************************************/

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define N 110000
using namespace std;
struct num
{
int end,next;
}b[N*10];
int a[N],id[N],num[N],pt[N],Top,cou,n;
bool visit[N];
char s1[10];
int main()
{
//freopen("data1.in","r",stdin);
void addeage(int x,int y);
void dfs(int k);
int get_sum(int x);
int update(int x,int val);
while(scanf("%d",&n)!=EOF)
{
memset(pt,-1,sizeof(pt));
Top=0;
for(int i=1;i<=n-1;i++)
{
int x,y;
scanf("%d %d",&x,&y);
addeage(x,y);
addeage(y,x);
}
cou=0;
memset(visit,false,sizeof(visit));
dfs(1);
int m,k;
scanf("%d",&m);
for(int i=1;i<=n;i++)
{
update(i,1);
}
while(m--)
{
scanf("%s %d",s1,&k);
int res;
if(s1[0]=='Q')
{
res=get_sum(id[k]+num[k]-1) - get_sum(id[k]-1);
printf("%d\n",res);
}else if(s1[0]=='C')
{
res = get_sum(id[k]) - get_sum(id[k]-1);
if(res==0)
{
update(id[k],1);
}else
{
update(id[k],-1);
}
}
}
}
return 0;
}
void addeage(int x,int y)
{
b[Top].end= y; b[Top].next = pt[x];
pt[x] = Top; Top++;
}
void dfs(int k)
{
id[k] = ++cou;
int pre = cou;
visit[k] = true;
for(int i=pt[k]; i!=-1; i=b[i].next)
{
if(!visit[b[i].end])
{

dfs(b[i].end);
}
}
num[k] = cou - pre + 1;
}
int find(int x)
{
return x&(-x);
}
int get_sum(int x)
{
int s=0;
while(x>0)
{
s+=a[x];
x-=find(x);
}
return s;
}
void update(int x,int val)
{
while(x<=n)
{
a[x] += val;
x += find(x);
}
}

POJ 3321 Apple Tree (二)