关于树链剖分模板的问题

回复帖子

@邹桐 2019-08-31 19:10 回复

第一个操作(将x与y路径上所有点加z)我是这样写的:

(其中pos表示剖分后的新的下标,top表示链顶,f[i][0]表示i的父亲)

long long Add(int x,int y,long long z){
    int l=lca(x,y);
    long long ret=0;
    while(top[x]!=top[l]){
        add(1,1,n,pos[top[x]],pos[x],z);
        x=fa[top[x]][0];
    }
    add(1,1,n,pos[l],pos[x],z);
    //对x到lca进行加法
    while(top[y]!=top[l]){
        add(1,1,n,pos[top[y]],pos[y],z);
        y=fa[top[y]][0];
    }
    add(1,1,n,pos[l],pos[y],z);
    //对y到lca进行加法
    add(1,1,n,pos[l],pos[l],-z);
    //因为lca算了两次 所以减去一次
    return ret;
}

并且确定其他的都写对了 (因为我重写了一个Add然后就没问题了)

请问一下这样写哪里错了?谢谢!

@邹桐 2019-08-31 19:18 回复 举报

@NaCly_Fish 蒟蒻刚学,不知道简单的做法QwQ(所以巨佬可不可以解释一下我为什么错了吗,谢谢

@GKxx 2019-08-31 20:08 回复 举报

应该是你别的地方写错了。我把我的代码里这一块改成你的写法之后也是AC的

@GKxx 2019-08-31 20:12 回复 举报

您可以学习一下如何用树剖求lca,然后您就知道这个操作怎么写更快了,不需要额外写倍增的,也不要单独求lca

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。