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

zxj015

 
 
 

日志

 
 

poj 3321 Apple Tree 树状数组  

2011-04-06 23:33:46|  分类: 数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一棵树,开始时每个结点都有一个苹果,输入C x表示更新x结点,若x结点有苹果,把该结点苹果摘掉,若该节点无苹果,在该节点上增加一个新的苹果。输入Q x表示以该节点为根的子树有多少个苹果。伸手便
该题主要问题是如何把一棵树转化为树状数组,之后便可以直接运用树状数组来求区间的和。转化的方法是用dfs深搜遍历树,每一个结点要做两次标记,第一次访问到时标记该结点,即为该结点在树状数组中的起始位置,第二次当dfs深搜返回时又一次标记,即为该结点在树状数组中末位置,始末位置之间即代表了以该结点为根的子树的所有结点。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
const int MAX = 100005;
 
struct{
    int v, nxt;
}edge[2*MAX];
int k = 1, edgeHead[MAX];
int n, m, dep, c[MAX];
int low[MAX], high[MAX];
bool pick[MAX], vis[MAX];
 
void dfs(int u){    
    low[u] = ++ dep;   //  第一次搜到第u个节点时的深度dep,为这个节点管辖区间的上限low[i]。
    vis[u] = true;
    for(int i = edgeHead[u]; i; i = edge[i].nxt)
        if(!vis[edge[i].v])
            dfs(edge[i].v);
    high[u] = dep;     //  最后搜回来后的深度dep,为这个节点管辖区间的下限high[i]。
}

int lowbit(int x){
    return x & (-x);
}
 
void add(int i, int w){
    while(i <= n){
        c[i] += w;
        i += lowbit(i);
    }
}
 
int sum(int i){
    int ans = 0;
    while(i > 0){
        ans += c[i];
        i -= lowbit(i);
    }
    return ans;
}
 
int main(){
    int i, u, v, ans;
    scanf("%d", &n);
    for(i = 1; i < n; i ++){
        scanf("%d%d", &u, &v);
        edge[k].v = v;
        edge[k].nxt = edgeHead[u];
        edgeHead[u] = k ++;
    }
    for(i = 1; i <= n; i ++)
        add(i, 1);
    dep = 0;
    dfs(1);
    scanf("%d", &m);
    while(m --){
        char ord;
        getchar();
        ord=getchar();
        scanf("%d",&u);
        if(ord == 'C'){
            if(pick[u]){
                add(low[u], 1);
                pick[u] = false;
            }else{
                add(low[u], -1);
                pick[u] = true;
            }
        }else{
            ans = sum(high[u]) - sum(low[u]-1);
            printf("%d\n", ans);
        }
    }
    system("pause"); 
    return 0;
}

  评论这张
 
阅读(268)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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