POJ 3321 Apple Tree(dfs序树状数组)

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=10486

题意:一颗有n个分支的苹果树,根为1,每个分支只有一个苹果,给出n-1个分支的关系和给出m个操作,Q x表示询问x的子树(包括x)苹果的数量,C x表示若分支x上有苹果,则摘下来,若没有则会生出一个,输出每个询问的值。

DFS序

每个子树对应的孩子节点包括根用dfs序存在连续区间中,用树状数组维护区间

 //#pragma comment(linker, "/STACK:167772160")//手动扩栈~~~~hdu 用c++交
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <algorithm>
#include <vector>
// #include<malloc.h>
// #include <conio.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define LL long long
const int inf = 0x3f3f3f3f;
const double eps = 1e-;
// const double pi = acos(-1);
const LL MOD = 1e8;
const int N=<<;
// const LL p = 1e9+7;
void fre() {
freopen("in.txt","r",stdin);
}
// inline int r(){
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
// return x*f;
// }
const int maxn = ; struct Edge{
int v,next;
} e[maxn*]; int head[maxn],tot,n;
bool vis[maxn];
int sum[maxn*];
int st[maxn],ed[maxn];
int inx; void init(){
for(int i=;i<maxn*;i++){
head[i>>]=-;
sum[i]=;
vis[i>>]=true;
}
tot=;
inx=;
} void add(int u,int v){
e[tot].v=v;
e[tot].next=head[u];
head[u]=tot++;
} void dfs(int rt,int fa){
st[rt]=++inx;
for(int i=head[rt];~i;i=e[i].next){
int v=e[i].v;
if(v==fa) continue;
dfs(v,rt);
}
ed[rt]=++inx;
} int lowbit(int x){
return x & -x;
} int query(int x){
int ans=;
while(x>=){
ans+=sum[x];
x -= lowbit(x);
}
return ans;
} void update(int x,int val){
while(x<=inx){
sum[x]+=val;
x+=lowbit(x);
}
} int main(){
// fre();
while(~scanf("%d",&n)){
init();
int u,v;
for(int i=;i<n-;i++){
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs(,-);
for(int i=;i<=n;i++)
update(st[i],);
int q;
char c;
int x;
scanf("%d",&q);
while(q--){
getchar();
scanf("%c%d",&c,&x);
if(c=='Q'){
int ans=query(ed[x])-query(st[x]-);
printf("%d\n",ans);
}
else{
if(vis[x]){
update(st[x],-);
}
else
update(st[x],);
vis[x]=!vis[x];
}
}
}
return ;
}
上一篇:记录java/javascript让浮点数显示两位小数的方法


下一篇:关于jquery文件上传插件 uploadify 3.1的使用