警示后人

P3384 【模板】重链剖分/树链剖分

CC__DIAMOND @ 2024-07-19 19:17:39

在修改两节点间路径时不应该是

while(top[x]!=top[y]) {
            if(dep[top[x]]>dep[top[y]]) swap(x,y);
            vals.add(dfn[top[y]],dfn[y],v);
            y=fa[top[y]];
        }
        if(dep[top[x]]>dep[top[y]) swap(x,y);
        vals.add(dfn[x],dfn[y],v);

而应该是

while(top[x]!=top[y]) {
            if(dep[top[x]]>dep[top[y]]) swap(x,y);
            vals.add(dfn[top[y]],dfn[y],v);
            y=fa[top[y]];
        }
        if(dep[x]>dep[y]) swap(x,y);
        vals.add(dfn[x],dfn[y],v);

by KobeBeanBryantCox @ 2024-08-04 19:09:10

thx


|