如果您 60 RE #1 #2 #3 #6情况6

如果您和我的写法类似，都在连边时将小的那棵树 dfs 删除主席树，那么请注意此时可能出现一个点被删除多次的情况。

我的写法：

CPP

inline int newnode() {
    if(top) {
        int x = stk[top--];
        return x;
    }
    else return ++cnt;
}

inline void del(int& o) {
    t[o].val = 0;
    //注意这里是直接删除，然后放进垃圾桶里的
    stk[++top] = o;
    o = 0;
}

inline void delnode(int& o) {
    if(t[o].ls) delnode(t[o].ls);
    if(t[o].rs) delnode(t[o].rs);
    del(o);
}

inline void deltree(int u, int f) {
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(v == f) continue;
        deltree(v, u);
    }
    delnode(root[u]);
}

由于主席树上一个点可能被公用多次，因此可能被删除多次，这样会使后面的更新中发生错误。

因此要记录一下每个点是否已经被删除。如果已经被删除，那就不用放进栈里了。可以用一个

vis

数组实现。

正确写法：

CPP

inline int newnode() {
    if(top) {
        int x = stk[top--];
        //
        vis[x] = false;
        //
        return x;
    }
    else return ++cnt;
}

inline void del(int& o) {
    t[o].val = 0;
    //注意这里
    if(!vis[o]) vis[o] = true, stk[++top] = o;
    //
    o = 0;
}

inline void delnode(int& o) {
    if(t[o].ls) delnode(t[o].ls);
    if(t[o].rs) delnode(t[o].rs);
    del(o);
}

inline void deltree(int u, int f) {
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(v == f) continue;
        deltree(v, u);
    }
    delnode(root[u]);
}

如果您 60 RE #1 #2 #3 #6情况6

讨论操作

回复

相关推荐

如果您 60 RE #1 #2 #3 #6情况6