树剖萌新求调

I_never_left @ 2024-02-02 10:14:42

#include <bits/stdc++.h>//用重剖把树分成链进行线段树

using namespace std;

#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)

typedef long long LL;

const int N = 400010;

LL e[N << 1], ne[N << 1], h[N << 1], tot;
LL n, m, rt, Mod, cnt;
LL fa[N], son[N], si[N], dep[N];
LL top[N], id[N], dfn[N], a[N];
struct tree {
    LL s, lz;
} t[N << 2];

void add(LL u, LL v) {
    e[++ tot] = v, ne[tot] = h[u], h[u] = tot;
}

//树剖
void dfs1(LL u, LL ff) {
    fa[u] = ff, si[u] = 1, dep[u] = dep[ff] + 1;
    for(LL i = h[u]; i; i = ne[i]) {
        LL v = e[i];
        if(v == ff) continue;
        dfs1(v, u); si[u] += si[v];
        if(si[son[u]] < si[v]) son[u] = v;
    }
}

void dfs2(LL u, LL topf) {
    top[u] = topf, dfn[u] = ++ tot, id[tot] = u;
    if(son[u]) dfs2(son[u], topf);
    for(LL i = h[u]; i; i = ne[i]) {
        LL v = e[i];
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

//线段树
void build(LL p, LL l, LL r) {
    if(l == r) {
        t[p].s = a[id[l]] % Mod;
        return ;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    t[p].s = (t[ls].s + t[rs].s + Mod) % Mod;
}

void pushdown(LL p, LL l, LL r) {
    if(t[p].lz) {
        t[ls].lz += t[p].lz; t[rs].lz += t[p].lz;
        t[ls].s += t[p].lz * (mid - l + 1);
        t[rs].s += t[p].lz * (r - mid);
        t[ls].s %= Mod; t[rs].s %= Mod;
        t[p].lz = 0;
    }
}

void modify(LL p, LL l, LL r, LL s, LL e, LL x) {
    if(s <= l && r <= e) {
        t[p].lz = (t[p].lz + x) % Mod;
        t[p].s = (t[p].s + x * (r - l + 1)) % Mod;
        return ;
    }

    pushdown(p, l, r);
    if(mid >= s) modify(ls, l, mid, s, e, x);
    if(mid < e) modify(rs, mid + 1, r, s, e, x);
    t[p].s = (t[ls].s + t[rs].s + Mod) % Mod;
}

int query(LL p, LL l, LL r, LL s, LL e) {
    LL res = 0;
    if(s <= l && r <= e) return t[p].s;
    pushdown(p, l, r);
    if(mid >= s) res += query(ls, l, mid, s, e);
    if(e > mid) res += query(rs, mid + 1, r, s, e);
    return res % Mod;
}

void modify(LL x, LL y, LL w) {
    while(top[x] != top[y]) {
        if(dep[fa[top[x]]] < dep[fa[top[y]]]) swap(x, y);
        modify(1, 1, n, dfn[top[x]], dfn[x], w);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    modify(1, 1, n, dfn[top[x]], dfn[y], w);
}

int query(int x, int y) {
    LL res = 0;
    while(top[x] != top[y]) {
        if(dep[fa[top[x]]] < dep[fa[top[y]]]) swap(x, y);
        res = (res + query(1, 1, n, dfn[top[x]], dfn[x])) % Mod;
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    res = (res + query(1, 1, n, dfn[x], dfn[y])) % Mod;
    return res;
}

int main() {
    scanf("%lld%lld%lld%lld", &n, &m, &rt, &Mod);
    for(LL i = 1; i <= n; ++ i) scanf("%lld", &a[i]);
    for(LL i = 1; i < n; ++ i) {
        LL u, v;
        scanf("%lld%lld", &u, &v);
        add(u, v);
        add(v, u);
    }
    dfs1(rt, 0);dfs2(rt, rt);build(1, 1, n);
    for(LL i = 1; i <= m; ++ i) {
        LL op, x, y, z;
        scanf("%lld", &op);
        if(op == 1) {
            scanf("%lld%lld%lld", &x, &y, &z);
            modify(x, y, z);
        } else if(op == 2) {
            scanf("%lld%lld", &x, &y);
            printf("%lld\n", query(x, y));
        } else if(op == 3) {
            scanf("%lld%lld", &x, &z);
            modify(1, 1, n, dfn[x], dfn[x] + si[x] - 1, z % Mod);
        } else {
            scanf("%lld", &x);
            printf("%lld\n", query(1, 1, n, dfn[x], dfn[x] + si[x] - 1));
        }
    }
    return 0;
}

by Elairin176 @ 2024-02-02 11:03:17

@_AC_problemer

#include <bits/stdc++.h>//用重剖把树分成链进行线段树

using namespace std;

#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)

typedef long long LL;

const int N = 400010;

LL e[N << 1], ne[N << 1], h[N << 1], tot;
LL n, m, rt, Mod, cnt;
LL fa[N], son[N], si[N], dep[N];
LL top[N], id[N], dfn[N], a[N];
struct tree {
    LL s, lz;
} t[N << 2];

void add(LL u, LL v) {
    e[++ tot] = v, ne[tot] = h[u], h[u] = tot;
}

//树剖
void dfs1(LL u, LL ff) {
    fa[u] = ff, si[u] = 1, dep[u] = dep[ff] + 1;
    for(LL i = h[u]; i; i = ne[i]) {
        LL v = e[i];
        if(v == ff) continue;
        dfs1(v, u); si[u] += si[v];
        if(si[son[u]] < si[v]) son[u] = v;
    }
}

void dfs2(LL u, LL topf) {
    top[u] = topf, dfn[u] = ++ tot, id[tot] = u;
    if(son[u]) dfs2(son[u], topf);
    for(LL i = h[u]; i; i = ne[i]) {
        LL v = e[i];
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

//线段树
void build(LL p, LL l, LL r) {
    if(l == r) {
        t[p].s = a[id[l]] % Mod;
        return ;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    t[p].s = (t[ls].s + t[rs].s + Mod) % Mod;
}

void pushdown(LL p, LL l, LL r) {
    if(t[p].lz) {
        t[ls].lz += t[p].lz; t[rs].lz += t[p].lz;
        t[ls].lz%=Mod,t[rs].lz%=Mod;
        t[ls].s += t[p].lz * (mid - l + 1)%Mod;
        t[rs].s += t[p].lz * (r - mid)%Mod;
        t[ls].s %= Mod; t[rs].s %= Mod;
        t[p].lz = 0;
    }
}

void modify(LL p, LL l, LL r, LL s, LL e, LL x) {
    if(l>e||r<s||l>r){
        return;
    }
    if(s <= l && r <= e) {
        t[p].lz = (t[p].lz + x) % Mod;
        t[p].s = (t[p].s + x * (r - l + 1)%Mod) % Mod;
        return ;
    }

    pushdown(p, l, r);
    modify(ls, l, mid, s, e, x);
    modify(rs, mid + 1, r, s, e, x);
    t[p].s = (t[ls].s + t[rs].s + Mod) % Mod;
}

int query(LL p, LL l, LL r, LL s, LL e) {
    if(l>e||r<s||l>r){
        return 0;
    }
    LL res = 0;
    if(s <= l && r <= e) return t[p].s;
    pushdown(p, l, r);
    res += query(ls, l, mid, s, e);
    res += query(rs, mid + 1, r, s, e);
    return res % Mod;
}

void modify(LL x, LL y, LL w) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        modify(1, 1, n, dfn[top[x]], dfn[x], w);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    modify(1, 1, n, dfn[x], dfn[y], w);
}

int query(int x, int y) {
    LL res = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        res = (res + query(1, 1, n, dfn[top[x]], dfn[x])) % Mod;
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    res = (res + query(1, 1, n, dfn[x], dfn[y])) % Mod;
    return res;
}

int main() {
    scanf("%lld%lld%lld%lld", &n, &m, &rt, &Mod);
    for(LL i = 1; i <= n; ++ i) scanf("%lld", &a[i]);
    for(LL i = 1; i < n; ++ i) {
        LL u, v;
        scanf("%lld%lld", &u, &v);
        add(u, v);
        add(v, u);
    }
    tot=0;
    dfs1(rt, 0);dfs2(rt, rt);build(1, 1, n);
    for(LL i = 1; i <= m; ++ i) {
        LL op, x, y, z;
        scanf("%lld", &op);
        if(op == 1) {
            scanf("%lld%lld%lld", &x, &y, &z);
            modify(x, y, z);
        } else if(op == 2) {
            scanf("%lld%lld", &x, &y);
            printf("%lld\n", query(x, y));
        } else if(op == 3) {
            scanf("%lld%lld", &x, &z);
            modify(1, 1, n, dfn[x], dfn[x] + si[x] - 1, z % Mod);
        } else {
            scanf("%lld", &x);
            printf("%lld\n", query(1, 1, n, dfn[x], dfn[x] + si[x] - 1));
        }
    }
    return 0;
}

by I_never_left @ 2024-02-02 11:06:35

@Eirin_Yagokoro 哪里错了

by Elairin176 @ 2024-02-02 11:09:12

@_AC_problemer 您求答案时，判断了 fa[top] 的深度，但这是错的，应判断 top 的深度。再就是 modify 中您最后的一段修改跳到了 top[x]，应该是 x。
对于线段树部分，应当加入对边界的判断。
应该是这些问题了，没太刻意去记。

by I_never_left @ 2024-02-02 19:18:05

@Eirin_Yagokoro 过了，感谢！