POJ 3321 Apple Tree dfs序的应用

题目链接

dfs序 说来很简单,却从来没有想到过。必须得深刻反省一下到底自己学了些啥。


题目大意是给你一棵树,动态统计某个子树的节点权值和。

同上一道题,裸算法。


利用dfs把一个树应设在一个序列上,方法是对每一次进栈出栈加一个时间戳,在这之间的点都是它的子节点。

然后就变成了动态统计区间和的问题了,

据说线段树会超。。

但是这种简单的求和问题,树状数组绝对是不二之选,用不着去折腾线段树了。


#include <cstdio>
#include <cstdlib>
#define N 210100
struct NODE {
    int v,next;
} a[N],st[N];
int h[N],t[N],P1[N],P2[N];
int tt,n,m,stn;

void dfs(int v) {
    P1[v]=++tt;
    for ( int p = a[v].next; p; p=st[p].next ) dfs(st[p].v);
    P2[v]=tt;
    return;
}

inline int l(int i) {
    return i & -i;
}

void update(int x,int k) {
    while (x<=n) {
        t[x] += k;
        x += l(x);
    }
}

int gs(int x) {
    int s =0;
    while ( x) {
        s += t[x];
        x -= l(x);
    }
    return s;
}

int main() {
    scanf("%d",&n);
    for ( int i(1); i<n; i++) {
        int a1,a2;
        scanf("%d%d",&a1,&a2);
        st[++stn].v = a2;
        st[stn].next = a[a1].next;
        a[a1].next = stn;
    }
    dfs(1);
    for ( int i(1); i<=n; i++) h[i]=1,update(P1[i],1);
    for ( scanf("%d\n",&m); m--;) {
        char ch;
        int x;
        scanf("%c%d\n",&ch,&x);
        if ( ch == 'C' ) {
            if ( h[x] ) update(P1[x],-1);
            else update(P1[x],1);
            h[x] = 1-h[x];
        } else
            printf("%d\n",gs(P2[x])-gs(P1[x]-1));
    }
    return 0;
}


注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-23 17:45
武汉商学院_2023
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议