注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

POJ 3321  

2010-02-26 16:45:13|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
应用树状数组的题目,需要先用dfs来通过时间的区间来区分树和子树的关系,利用时间建立树状数组求解即可
#include<cstdio>
#include<cstring>
int temp[100002],a[200002],n,m,pnt[200002],head[200002],nxt[200002],time[100002][2],tt=0,e=0;
int lowbit(int k){
    return k&(k^(k-1));
}
int sum(int k){
    int sum=0;
    while(k>0){
      sum+=a[k];
      k-=lowbit(k);
    }
    return sum;
}
void change(int position,int k){
    while(position<=2*n){
      a[position]+=k;
      position+=lowbit(position);
    }
}
inline void addedge(int s0,int t0){
      pnt[e]=t0;nxt[e]=head[s0];head[s0]=e++;
      pnt[e]=s0;nxt[e]=head[t0];head[t0]=e++;
}
void dfs(int k){
     if(!time[k][0]){
       time[k][0]=++tt;
       for(int i=head[k];i!=-1;i=nxt[i])
         dfs(pnt[i]);
       time[k][1]=++tt;
     }
}
int main(){
    scanf("%d",&n);
    memset(head,-1,sizeof(head));
    memset(nxt,-1,sizeof(nxt));
    for(int i=1;i<=n;i++){
      temp[i]=1;
      change(i,1);
      change(i+n,1);
    }
    int c,d;
    for(int i=1;i<n;i++){
      scanf("%d%d",&c,&d);
      addedge(c,d);
    }
    dfs(1);
    scanf("%d\n",&m);
    char cc,ww;
    for(int i=0;i<m;i++){
      scanf("%c %d",&cc,&d);
      getchar();
      if(cc=='C'){
        change(time[d][0],-temp[d]);
        change(time[d][1],-temp[d]);
        temp[d]=-temp[d];
      }
      else printf("%d\n",(sum(time[d][1])-sum(time[d][0])+(1+temp[d])/2)/2);
    }
    return 0;
}

  评论这张
 
阅读(1488)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017