萌新第一次学树剖，求调！

CznTree @ 2024-03-28 20:27:39

#include <bits/stdc++.h> 
#define IOS std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr) 
#define rep(i, a, b) for (int i = a; i <= b; i++) 
#define per(i, a, b) for (int i = a; i >= b; i--)
#define lc(x) x << 1ll 
#define rc(x) x << 1ll | 1ll
#define lowbit(x) ((x) & (-x))
#define int long long 
const int N = 1e5+ 7; 
struct Edge{
    int to, next; 
}edge[N << 1]; 
int head[N << 1]; 
int cnt, tot; 
int deep[N], size[N], son[N], fa[N], top[N], id[N]; 
int a[N]; 
int w[N]; 
int n, m, r, p; 
void add(int u, int v) 
{
    cnt++; 
    edge[cnt].to = v; 
    edge[cnt].next = head[u]; 
    head[u] = cnt; 
}

void dfs1(int u, int father){
    deep[u] = deep[father] + 1; 
    fa[u] = father; 
    size[u] = 1; 
    for(int i = head[u]; i; i = edge[i].next) {
        int now = edge[i].to; 
        if(now != father) {
            fa[now] = u; 
            dfs1(now, u); 
            size[u] += size[now]; 
            if(!son[u] || size[son[u]] < size[now]) {
                son[u] = now; 
            }
        }
    }
}

void dfs2(int u, int tops) {
    id[u] = ++tot; 
    w[tot] = a[u]; 
    top[u] = tops; 
    if(!son[u]) return ; 
    dfs2(son[u], tops); 
    for(int i = head[u]; i; i = edge[i].next) {
        int now = edge[i].to; 
        if(now != fa[u] && now != son[u]) {
            dfs2(now, now); 
        }
    }
}
struct Tree {
    int l, r; 
    int sum; 
    int lazy; 
}tree[N << 2];

void push_up(int i) {
    tree[i].sum = (tree[lc(i)].sum + tree[rc(i)].sum) % p; 
}

void push_down(int i) {
    if(tree[i].lazy) {
        int k = tree[i].lazy; 
        tree[lc(i)].lazy += k, tree[rc(i)].lazy += k;
        tree[lc(i)].lazy %= p, tree[rc(i)].lazy %= p; 
        tree[lc(i)].sum = (tree[lc(i)].r - tree[lc(i)].l + 1) * k, tree[lc(i)].sum %= p; 
        tree[rc(i)].sum = (tree[rc(i)].r - tree[rc(i)].l + 1) * k, tree[rc(i)].sum %= p; 
        tree[i].lazy = 0; 
    }
}

void build(int i, int L, int R) {
    tree[i].l = L, tree[i].r = R; 
    if(L == R) {
        tree[i].sum = w[L] % p; 
        return ; 
    }
    int mid = (L + R) >> 1; 
    build(lc(i), L, mid), build(rc(i), mid + 1, R); 
    push_up(i); 
}

void modify(int i, int L, int R, int k) {
    if(L <= tree[i].l && tree[i].r <= R) {
        tree[i].lazy += k; tree[i].lazy %= p; 
        tree[i].sum = (tree[i].r - tree[i].l + 1) * k; tree[i].sum %= p;
        return ; 
    }
    push_down(i); 
    if(tree[lc(i)].r >= L) modify(lc(i), L, R, k); 
    if(tree[rc(i)].l <= R) modify(rc(i), L, R, k); 
    push_up(i); 
}

int query(int i, int L, int R) {
    if(L <= tree[i].l && tree[i].r <= R) {
        tree[i].sum %= p; 
        return tree[i].sum; 
    }
    push_down(i); 
    int res = 0; 
    if(tree[lc(i)].r >= L) res += query(lc(i), L, R);
    if(tree[rc(i)].l <= R) res += query(rc(i), L, R); 
    return res; 
}

void Modify(int x, int y, int z) {
    while(top[x] != top[y]) {
        if(deep[top[x]] < deep[top[y]]) std::swap(x, y); 
        modify(1, id[top[x]], id[x], z); 
        x = fa[top[x]]; 
    }
    if(deep[x] > deep[y])   std::swap(x, y);  
    modify(1, id[x], id[y], z); 
}

int Query(int x, int y) {
    int res = 0; 
    while(top[x] != top[y]) {
        if(deep[top[x]] < deep[top[y]]) std::swap(x, y); 
        res += query(1, id[top[x]], id[x]); 
        res %= p; 
        x = fa[top[x]]; 
    }
    if(deep[x] > deep[y]) std::swap(x, y); 
    res += query(1, id[x], id[y]); 
    return res % p; 
}

void solve() { 
    std::cin >> n >> m >> r >> p; 
    rep(i, 1, n) {
        std::cin >> a[i];
    }
    rep(i, 1, n - 1) {
        int u, v; std::cin >> u >> v; 
        add(u, v), add(v, u); 
    }
    dfs1(r, 0); 
    dfs2(r, r); 
    build(1, 1, n); 
    while(m--) {
        int opt; 
        std::cin >> opt; 
        if(opt == 1) {
            int x, y, z; std::cin >> x >> y >> z; 
            Modify(x, y, z); 
        }
        if(opt == 2) {
            int x, y; std::cin >> x >> y; 
            std::cout << Query(x, y) << std::endl; 
        }
        if(opt == 3) {
            int x, z;   std::cin >> x >> z; 
            modify(1, id[x], id[x] + size[x] - 1, z); 
        }
        if(opt == 4) {
            int x; std::cin >> x; 
            std::cout << query(1, id[x], id[x] + size[x] - 1) % p << std::endl; 
        }
    }
}
signed main() {
    IOS; 
    solve(); 
    return 0; 
}

by CznTree @ 2024-03-28 20:28:38

样例输出：

2
5

（悲

by OldDriverTree @ 2024-03-28 20:34:52

@czn__ pushdown sum维护错了

by OldDriverTree @ 2024-03-28 20:35:34

@czn__ 还有modify，还要加上原来的 sum

by Nt_Tsumiki @ 2024-03-28 20:35:57

@czn__ 72，73，92 行改成 +=

#include <bits/stdc++.h> 
#define IOS std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr) 
#define rep(i, a, b) for (int i = a; i <= b; i++) 
#define per(i, a, b) for (int i = a; i >= b; i--)
#define lc(x) x << 1ll 
#define rc(x) x << 1ll | 1ll
#define lowbit(x) ((x) & (-x))
#define int long long 
const int N = 1e5+ 7; 
struct Edge{
    int to, next; 
}edge[N << 1]; 
int head[N << 1]; 
int cnt, tot; 
int deep[N], size[N], son[N], fa[N], top[N], id[N]; 
int a[N]; 
int w[N]; 
int n, m, r, p; 
void add(int u, int v) 
{
    cnt++; 
    edge[cnt].to = v; 
    edge[cnt].next = head[u]; 
    head[u] = cnt; 
}

void dfs1(int u, int father){
    deep[u] = deep[father] + 1; 
    fa[u] = father; 
    size[u] = 1; 
    for(int i = head[u]; i; i = edge[i].next) {
        int now = edge[i].to; 
        if(now != father) {
            fa[now] = u; 
            dfs1(now, u); 
            size[u] += size[now]; 
            if(!son[u] || size[son[u]] < size[now]) {
                son[u] = now; 
            }
        }
    }
}

void dfs2(int u, int tops) {
    id[u] = ++tot; 
    w[tot] = a[u]; 
    top[u] = tops; 
    if(!son[u]) return ; 
    dfs2(son[u], tops); 
    for(int i = head[u]; i; i = edge[i].next) {
        int now = edge[i].to; 
        if(now != fa[u] && now != son[u]) {
            dfs2(now, now); 
        }
    }
}
struct Tree {
    int l, r; 
    int sum; 
    int lazy; 
}tree[N << 2];

void push_up(int i) {
    tree[i].sum = (tree[lc(i)].sum + tree[rc(i)].sum) % p; 
}

void push_down(int i) {
    if(tree[i].lazy) {
        int k = tree[i].lazy; 
        tree[lc(i)].lazy += k, tree[rc(i)].lazy += k;
        tree[lc(i)].lazy %= p, tree[rc(i)].lazy %= p; 
        tree[lc(i)].sum += (tree[lc(i)].r - tree[lc(i)].l + 1) * k, tree[lc(i)].sum %= p; 
        tree[rc(i)].sum += (tree[rc(i)].r - tree[rc(i)].l + 1) * k, tree[rc(i)].sum %= p; 
        tree[i].lazy = 0; 
    }
}

void build(int i, int L, int R) {
    tree[i].l = L, tree[i].r = R; 
    if(L == R) {
        tree[i].sum = w[L] % p; 
        return ; 
    }
    int mid = (L + R) >> 1; 
    build(lc(i), L, mid), build(rc(i), mid + 1, R); 
    push_up(i); 
}

void modify(int i, int L, int R, int k) {
    if(L <= tree[i].l && tree[i].r <= R) {
        tree[i].lazy += k; tree[i].lazy %= p; 
        tree[i].sum += (tree[i].r - tree[i].l + 1) * k; tree[i].sum %= p;
        return ;
    }
    push_down(i); 
    if(tree[lc(i)].r >= L) modify(lc(i), L, R, k); 
    if(tree[rc(i)].l <= R) modify(rc(i), L, R, k); 
    push_up(i); 
}

int query(int i, int L, int R) {
    if(L <= tree[i].l && tree[i].r <= R) {
        tree[i].sum %= p; 
        return tree[i].sum; 
    }
    push_down(i); 
    int res = 0; 
    if(tree[lc(i)].r >= L) res += query(lc(i), L, R);
    if(tree[rc(i)].l <= R) res += query(rc(i), L, R); 
    return res; 
}

void Modify(int x, int y, int z) {
    while(top[x] != top[y]) {
        if(deep[top[x]] < deep[top[y]]) std::swap(x, y); 
        modify(1, id[top[x]], id[x], z); 
        x = fa[top[x]]; 
    }
    if(deep[x] > deep[y])   std::swap(x, y);  
    modify(1, id[x], id[y], z); 
}

int Query(int x, int y) {
    int res = 0; 
    while(top[x] != top[y]) {
        if(deep[top[x]] < deep[top[y]]) std::swap(x, y); 
        res += query(1, id[top[x]], id[x]); 
        res %= p; 
        x = fa[top[x]]; 
    }
    if(deep[x] > deep[y]) std::swap(x, y); 
    res += query(1, id[x], id[y]); 
    return res % p; 
}

void solve() { 
    std::cin >> n >> m >> r >> p; 
    rep(i, 1, n) {
        std::cin >> a[i];
    }
    rep(i, 1, n - 1) {
        int u, v; std::cin >> u >> v; 
        add(u, v), add(v, u); 
    }
    dfs1(r, 0); 
    dfs2(r, r); 
    build(1, 1, n); 
    while(m--) {
        int opt; 
        std::cin >> opt; 
        if(opt == 1) {
            int x, y, z; std::cin >> x >> y >> z; 
            Modify(x, y, z); 
        }
        if(opt == 2) {
            int x, y; std::cin >> x >> y; 
            std::cout << Query(x, y) << std::endl; 
        }
        if(opt == 3) {
            int x, z;   std::cin >> x >> z; 
            modify(1, id[x], id[x] + size[x] - 1, z); 
        }
        if(opt == 4) {
            int x; std::cin >> x; 
            std::cout << query(1, id[x], id[x] + size[x] - 1) % p << std::endl; 
        }
    }
}
signed main() {
    IOS; 
    solve(); 
    return 0; 
}

by CznTree @ 2024-03-28 20:37:54

@Nt_Tsumiki 完了，我变成弱智了

by CznTree @ 2024-03-28 20:38:41

@OldDriverTree @Nt_Tsumiki 谢谢！（最近脑子不正常了