萌新刚学树剖求助（玄 2 关

WydnksqhbD @ 2024-05-08 14:45:02

2
19

#include <bits/stdc++.h>
#define int long long
#define ls p << 1
#define rs p << 1 | 1

using namespace std;

const int N = 1e5 + 5;

int n, m, root, P, _index;

int a[N], f[N], h[N], siz[N], t[N], dfn[N], rdfn[N], d[N], tree[N], change[N];

vector <int> v[N];

void orz (int p) {
    tree[p] %= P;
    change[p] %= P;
}

void pushup (int p) {
    tree[p] = tree[ls] + tree[rs];
    orz (p);
}

void pushdown (int len, int p) {
    change[ls] += change[p];
    change[rs] += change[p];
    tree[ls] += change[p] * (len - len >> 1);
    tree[rs] += change[p] * (len >> 1);
    change[p] = 0;
    orz (p);
    orz (ls);
    orz (rs);
}

void build (int l = 1, int r = n, int p = 1) {
    if (l == r) {
        tree[p] = a[rdfn[l]];
    } else {
        int mid = (l + r) >> 1;
        build (l, mid, ls);
        build (mid + 1, r, rs);
        pushup (p);
    }
}

void update (int l, int r, int k, int cl = 1, int cr = n, int p = 1) {
    if (l > r) { swap (l, r); }
    if (cl > r || cr < l) {
        return;
    } else if (cl >= l && cr <= r) {
        tree[p] += k * (cr - cl + 1);
        change[p] += k;
    } else {
        int mid = (cl + cr) >> 1;
        pushdown (cr - cl + 1, p);
        update (l, r, k, cl, mid, ls);
        update (l, r, k, mid + 1, cr, rs);
        pushup (p);
    }
}

int query (int l, int r, int cl = 1, int cr = n, int p = 1) {
    if (l > r) { swap (l, r); }
    if (cl > r || cr < l) {
        return 0;
    } else if (cl >= l && cr <= r) {
        return tree[p];
    } else {
        int mid = (cl + cr) >> 1;
        pushdown (cr - cl + 1, p);
        return (query (l, r, cl, mid, ls) + query (l, r, mid + 1, cr, rs)) % P;
    }
}

void dfs1 (int cur, int father) {
    f[cur] = father;
    siz[cur] = 1;
    d[cur] = f[father] + 1;

    for (int i = 0; i < v[cur].size (); ++ i) {
        if (v[cur][i] != father) {
            dfs1 (v[cur][i], cur);
            siz[cur] += siz[v[cur][i]];

            if (siz[v[cur][i]] > siz[h[cur]]) { h[cur] = v[cur][i]; }
        }
    }
}

void dfs2 (int cur, int top) {
    dfn[cur] = ++ _index;
    rdfn[_index] = cur;
    t[cur] = top;

    if (h[cur]) {
        dfs2 (h[cur], top);

        for (int i = 0; i < v[cur].size (); ++ i) {
            if (v[cur][i] != f[cur] && v[cur][i] != h[cur]) {
                dfs2 (v[cur][i], v[cur][i]);
            }
        }
    }
}

void add (int x, int y, int z) {
    while (t[x] != t[y]) {
        if (d[x] < d[y]) { swap (x, y); }
        update (dfn[t[x]], dfn[x], z);
        x = f[t[x]];
    }

    update (dfn[x], dfn[y], z);
}

int sum (int x, int y) {
    int total = 0;

    while (t[x] != t[y]) {
        if (d[x] < d[y]) { swap (x, y); }
        total += query (dfn[t[x]], dfn[x]);
        total %= P;
        x = f[t[x]];
    }

    return total + query (dfn[x], dfn[y]);
}

signed main () {
    cin >> n >> m >> root >> P;

    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
    }

    for (int x, y, i = 1; i < n; ++ i) {
        cin >> x >> y;
        v[x].push_back (y);
        v[y].push_back (x);
    }

    dfs1 (root, 0);

    dfs2 (root, 0);

    build ();

    for (int op, x, y, z; m; -- m) {
        cin >> op >> x;

        if (op == 1) {
            cin >> y >> z;
            add (x, y, z);
        } else if (op == 2) {
            cin >> y;
            cout << sum (x, y) % P << endl;
        } else if (op == 3) {
            cin >> y;
            update (dfn[x], dfn[x] + siz[x] - 1, y);
        } else {
            cout << query (dfn[x], dfn[x] + siz[x] - 1) % P << endl;
        }
    }

    return 0;
}

by WydnksqhbD @ 2024-05-08 15:24:17

@红黑树 ？

by WydnksqhbD @ 2024-05-08 15:25:09

len - len >> 1 有何问题嘛（

by qiuzijin2026 @ 2024-05-08 15:25:26

@红黑树 它没问题

by WydnksqhbD @ 2024-05-08 15:25:39

@qiuzijin2026 有问题

by WydnksqhbD @ 2024-05-08 15:25:58

改完就 21 了？

by WydnksqhbD @ 2024-05-08 15:26:42

难道 len - len >> 1 不是 len - len / 2？

by WydnksqhbD @ 2024-05-08 15:27:31

然后 WA 掉了（）

by qiuzijin2026 @ 2024-05-08 15:27:56

@WydnksqhbD 运算符优先级，+-的级别大于>>，我脑袋抽风了

by __Chx__ @ 2024-05-08 15:28:15

#include <bits/stdc++.h>
#define int long long
#define ls p << 1
#define rs p << 1 | 1

using namespace std;

const int N = 1e5 + 5;

int n, m, root, P, _index;

int a[N], f[N], h[N], siz[N], t[N], dfn[N], rdfn[N], d[N], tree[N<<2], change[N<<2];

vector <int> v[N];

void orz (int p) {
    tree[p] %= P;
    change[p] %= P;
}

void pushup (int p) {
    tree[p] = tree[ls] + tree[rs];
    orz (p);
}

void pushdown (int len, int p) {
    change[ls] += change[p];
    change[rs] += change[p];
    tree[ls] += change[p] * (len - (len >> 1));
    tree[rs] += change[p] * (len >> 1);
    change[p] = 0;
    orz (p);
    orz (ls);
    orz (rs);
}

void build (int l = 1, int r = n, int p = 1) {
    if (l == r) {
        tree[p] = a[rdfn[l]];
    } else {
        int mid = (l + r) >> 1;
        build (l, mid, ls);
        build (mid + 1, r, rs);
        pushup (p);
    }
}

void update (int l, int r, int k, int cl = 1, int cr = n, int p = 1) {
    if (l > r) { swap (l, r); }
    if (cl > r || cr < l) {
        return;
    } else if (cl >= l && cr <= r) {
        tree[p] += k * (cr - cl + 1);
        change[p] += k;
        orz (p);
    } else {
        int mid = (cl + cr) >> 1;
        pushdown (cr - cl + 1, p);
        update (l, r, k, cl, mid, ls);
        update (l, r, k, mid + 1, cr, rs);
        pushup (p);
    }
}

int query (int l, int r, int cl = 1, int cr = n, int p = 1) {
    if (l > r) { swap (l, r); }
    if (cl > r || cr < l) {
        return 0;
    } else if (cl >= l && cr <= r) {
        return tree[p];
    } else {
        int mid = (cl + cr) >> 1;
        pushdown (cr - cl + 1, p);
        return (query (l, r, cl, mid, ls) + query (l, r, mid + 1, cr, rs)) % P;
    }
}

void dfs1 (int cur, int father) {
    f[cur] = father;
    siz[cur] = 1;
    d[cur] = d[father] + 1;

    for (int i = 0; i < v[cur].size (); ++ i) {
        if (v[cur][i] != father) {
            dfs1 (v[cur][i], cur);
            siz[cur] += siz[v[cur][i]];

            if (siz[v[cur][i]] > siz[h[cur]]) { h[cur] = v[cur][i]; }
        }
    }
}

void dfs2 (int cur, int top) {
    dfn[cur] = ++ _index;
    rdfn[_index] = cur;
    t[cur] = top;

    if (h[cur]) {
        dfs2 (h[cur], top);

        for (int i = 0; i < v[cur].size (); ++ i) {
            if (v[cur][i] != f[cur] && v[cur][i] != h[cur]) {
                dfs2 (v[cur][i], v[cur][i]);
            }
        }
    }
}

void add (int x, int y, int z) {
    while (t[x] != t[y]) {
        if (d[t[x]] < d[t[y]]) { swap (x, y); }
        update (dfn[t[x]], dfn[x], z);
        x = f[t[x]];
    }
    if(d[x] > d[y]) swap (x, y); 

    update (dfn[x], dfn[y], z);
}

int sum (int x, int y) {
    int total = 0;

    while (t[x] != t[y]) {
        if (d[t[x]] < d[t[y]]) { swap (x, y); }
        total += query (dfn[t[x]], dfn[x]);
        total %= P;
        x = f[t[x]];
    }
    if(d[x] > d[y]) swap (x, y); 

    return total + query (dfn[x], dfn[y]);
}

signed main () {
    cin >> n >> m >> root >> P;

    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
    }

    for (int x, y, i = 1; i < n; ++ i) {
        cin >> x >> y;
        v[x].push_back (y);
        v[y].push_back (x);
    }

    dfs1 (root, 0);

    dfs2 (root, root);

    build ();

    for (int op, x, y, z; m; -- m) {
        cin >> op >> x;

        if (op == 1) {
            cin >> y >> z;
            add (x, y, z);
        } else if (op == 2) {
            cin >> y;
            cout << sum (x, y) % P << endl;
        } else if (op == 3) {
            cin >> y;
            update (dfn[x], dfn[x] + siz[x] - 1, y);
        } else {
            cout << query (dfn[x], dfn[x] + siz[x] - 1) % P << endl;
        }
    }

    return 0;
}

by WydnksqhbD @ 2024-05-08 15:28:47

@qiuzijin2026 啊？颠覆认知