树剖写挂求助

话说我的测试点信息也是绝，不全部是漂亮的绿色，但是却是真的好看。

我是37分，不知道为什么错了。1,2,3点AC，4,5,6,7WA，8,9,10TLE，11AC。（样例过了）

我写树的风格可能和别人不太一样，敬请谅解。因此，我也做了一些通俗易懂的注释。

先放代码：

#include <iostream>
#include <vector>
#define int long long
using namespace std;

const int MAXN = 1e5 + 7;
int n, m, r, p, type, x, y, z;

struct node { // 我是直接放一个node里面
    int fa = -1, son = 0, val, newval, ord, top, siz, dep;
    vector<int> to;
} tree[MAXN]; // 树

// fa:父亲,son:重儿子,val:初始权值,newval:dfs二次编号后的权值,ord:dfs的二次编号(id),top:重链顶端,siz:子树大小,dep:结点深度

void insert(int l, int r) { // 链接两点
    tree[l].to.push_back(r);
    tree[r].to.push_back(l);
}

int dfs1(int fa, int idx) { // 返回size值，记录dep,fa,son,siz
    tree[idx].dep = tree[fa].dep + 1; tree[idx].fa = fa;
    int cnt = 0, mx = -1, midx = 0;
    for (int& i : tree[idx].to) {
        if (i != fa) {
            int k = dfs1(idx, i);
            if (k > mx) mx = k, midx = i;
            cnt += k;
        }
    }
    tree[idx].son = midx;
    return tree[idx].siz = cnt + 1;
}

int ordcnt = 0;

void dfs2(int top, int idx) { // 记录ord,top,newval
    tree[idx].top = top; tree[idx].ord = ++ordcnt; tree[ordcnt].newval = tree[idx].val;
    if (tree[idx].son != 0) dfs2(top, tree[idx].son);
    for (int& i : tree[idx].to) {
        if (i != tree[idx].fa && i != tree[idx].son) {
            dfs2(i, i);
        }
    }
}

int segtree[MAXN << 2]; // 线段树

void build(int l, int r, int idx) { // 建树
    if (l == r) segtree[idx] = tree[l].newval;
    else {
        int mid = l + r >> 1;
        build(l, mid, idx * 2);
        build(mid + 1, r, idx * 2 + 1);
        segtree[idx] = segtree[idx * 2] + segtree[idx * 2 + 1];
    }
}

int getsum(int l, int r, int idx, int l_, int r_) { // 俗称query，求l到r的区间和
    if (l_ > r || r_ < l) return 0;
    if (l <= l_ && r_ <= r) return segtree[idx];
    int mid = l_ + r_ >> 1;
    return getsum(l, r, idx * 2, l_, mid) + getsum(l, r, idx * 2 + 1, mid + 1, r_);
}

void change(int l, int r, int idx, int val, int l_, int r_) { // 俗称modify或update,让l到r区间加上val
    if (l_ > r || r_ < l) return;
    if (l_ == r_) { segtree[idx] += val; return; }
    int mid = l_ + r_ >> 1;
    change(l, r, idx * 2, val, l_, mid);
    change(l, r, idx * 2 + 1, val, mid + 1, r_);
    segtree[idx] = segtree[idx * 2] + segtree[idx * 2 + 1];
}

int getpath(int x, int y, int (*func)(int, int)) { // 俗称lca并用方便快捷简单函数指针操作重链
    int res = 0;
    while (tree[x].top != tree[y].top) {
        if (tree[tree[x].top].dep < tree[tree[y].top].dep) swap(x, y);
        res += func(tree[x].ord, tree[tree[x].top].ord);
        x = tree[tree[x].top].fa;
    }
    if (tree[x].ord > tree[y].ord) swap(x, y);
    res += func(tree[x].ord, tree[y].ord);
    return res;
}

signed main() {
    scanf("%lld %lld %lld %lld", &n, &m, &r, &p);
    for (int i = 1; i <= n; i++) scanf("%lld", &tree[i].val);
    for (int i = 1; i < n; i++) { int l, r; scanf("%lld %lld", &l, &r); insert(l, r); }
    tree[r].dep = 1;
    dfs1(r, r);
    dfs2(r, r);
    build(1, n, 1);
    while (m--) {
        scanf("%lld", &type);
        if (type == 1) {
            scanf("%lld %lld %lld", &x, &y, &z);
            getpath(x, y, [](int a, int b) { change(a, b, 1, z, 1, n); return 0ll; });
        }
        else if (type == 2) {
            scanf("%lld %lld", &x, &y);
            printf("%lld\n", getpath(x, y, [](int a, int b) { return getsum(a, b, 1, 1, n); }) % p);
        }
        else if (type == 3) {
            scanf("%lld %lld", &x, &y);
            change(tree[x].ord, tree[x].ord + tree[x].siz - 1, 1, y, 1, n);
        }
        else if (type == 4) {
            scanf("%lld", &x);
            printf("%lld\n", getsum(tree[x].ord, tree[x].ord + tree[x].siz - 1, 1, 1, n) % p);
        }
    }
}

不知道有没有巨佬愿意帮我调一下？

赏关。