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;
}


全部评论

相关推荐

不愿透露姓名的神秘牛友
07-03 16:46
今天本来好好的,结果带教老师当着众人的面,直接大声叫我的名字,我过去还没站稳,劈头盖脸就是一句:“你这搞的什么玩意啊!没带脑子上班吗”那语气、那眼神,仿佛我做了什么十恶不赦的大事。我到底干啥了?不过是一些小疏漏,谁刚开始实习不会犯错啊?可她倒好,不仅不耐心指导,还这样贬低我。我满心的热情和期待,瞬间被浇了个透心凉🥶我也是爹妈疼爱的宝贝,来实习是为了学习、成长,不是来被人随意羞辱的!真心希望遇到的带教老师能多些耐心和善意,毕竟谁都有从零开始的时候,这样的“教育”方式,真的只会让人越来越没自信
longerluck...:前几年实习(初创公司),我们老板每月不固定会举行会议,叫我们几个实习生谈一下生活看到或听到的一些事情,并给出看法,当时我就正常讲了下我所见到的,没有个人看法,老板直接当着众人的面骂了我,那时候我真是感觉尴尬的要死(毕竟还有其他正式员工在)后面没待多久我就提出离职(因为当时我还负责一个项目),我leader叫我不要走,说给我涨工资,我反正觉得这种公司我是待不下去了,官味太重了,最后我还是跑路
实习吐槽大会
点赞 评论 收藏
分享
Rena1ssanc...:对的,要是面评没太烂,勤更新简历等捞就行了,腾讯可以无限复活
点赞 评论 收藏
分享
06-17 00:26
门头沟学院 Java
程序员小白条:建议换下项目,智能 AI 旅游推荐平台:https://github.com/luoye6/vue3_tourism_frontend 智能 AI 校园二手交易平台:https://github.com/luoye6/vue3_trade_frontend GPT 智能图书馆:https://github.com/luoye6/Vue_BookManageSystem 选项目要选自己能掌握的,然后最好能自己拓展的,分布式这种尽量别去写,不然你只能背八股文了,另外实习的话要多投,尤其是学历不利的情况下,多找几段实习,最好公司title大一点的
无实习如何秋招上岸
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 13:15
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务