本地飞快 + 洛谷 TLE on #8910 球跳 /kel

As shown.

#include <bits/stdc++.h>
// #define int long long
using namespace std;
int len(int l, int r) { return r - l + 1; }
int ls(int u) { return u << 1; }
int rs(int u) { return u << 1 | 1; }
const int MAXN = 2e5 + 5;
int N, M, R, P;
vector<int> g[MAXN];
int val[MAXN];
//..dfs1
int fa[MAXN], dep[MAXN], sz[MAXN], hson[MAXN];
void dfs1(int u, int depth, int father) {
    dep[u] = depth;
    sz[u] = 1;
    fa[u] = father;
    hson[u] = -1;
    for (auto x : g[u])
        if (x != father) {
            dfs1(x, depth + 1, u);
            sz[u] += sz[x];
            if (hson[x] == -1 || sz[x] > sz[hson[u]])
                hson[u] = x;
        }
}
//..dfs2
int dfnum = 0;
int dfn[MAXN], top[MAXN], rnk[MAXN];
void dfs2(int u, int chtop) {
    top[u] = chtop;
    dfn[u] = ++dfnum;
    rnk[dfn[u]] = u;
    if (sz[u] != 1) {
        dfs2(hson[u], chtop);
        for (auto x : g[u])
            if (x != fa[u])
                if (x != hson[u])
                    dfs2(x, x);
    }
}
class Segtree {
  private:
    int n;
    vector<int> s, t;
    void maketag(const int k, int u, int l, int r) {
        // cout << l << ' ' << r << endl;
        s[u] += len(l, r) * k % P;
        s[u] %= P;
        t[u] += k;
        t[u] %= P;
    }
    void add(int u, int l, int r, const int L, const int R, const int k) {
        if (r < L || l > R)
            return;
        if (l >= L && r <= R) {
            maketag(k, u, l, r);
            return;
        }
        int mid = l + r >> 1;
        maketag(t[u], ls(u), l, mid);
        maketag(t[u], rs(u), mid + 1, r);
        t[u] = 0;
        add(ls(u), l, mid, L, R, k);
        add(rs(u), mid + 1, r, L, R, k);
        s[u] = s[ls(u)] + s[rs(u)];
        s[u] %= P;
    }
    int sum(int u, int l, int r, const int L, const int R) {
        if (r < L || l > R)
            return 0;
        if (l >= L && r <= R)
            return s[u];
        int mid = l + r >> 1;
        maketag(t[u], ls(u), l, mid);
        maketag(t[u], rs(u), mid + 1, r);
        t[u] = 0;
        return (sum(ls(u), l, mid, L, R) + sum(rs(u), mid + 1, r, L, R)) % P;
    }

  public:
    Segtree(int _size) {
        n = _size, s.resize((_size + 1) << 2), t.resize((_size + 1) << 2);
    }
    void add(const int __l, const int __r, const int __value) {
        add(1, 1, n, __l, __r, __value);
    }
    int sum(const int __l, const int __r) { return sum(1, 1, n, __l, __r); }
};
Segtree Tree(100);
int pw(int a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res *= a;
            res %= p;
        }
        a *= a;
        a %= p;
        b /= 2;
    }
    return res;
}
void TrAdd(int u, int k) {
    int l = dfn[u], r = dfn[u] + sz[u] - 1;
    Tree.add(l, r, k);
}
int TrSum(int u) {
    int l = dfn[u], r = dfn[u] + sz[u] - 1;
    return Tree.sum(l, r);
}
void RoadAdd(int x, int y, int k) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        Tree.add(dfn[top[x]], dfn[x], k);
        x = fa[top[x]];
    }
    int l = min(dfn[x], dfn[y]);
    int r = max(dfn[x], dfn[y]);
    Tree.add(l, r, k);
}
int RoadSum(int x, int y) {
    int res = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        res += Tree.sum(dfn[top[x]], dfn[x]);
        res %= P;
        x = fa[top[x]];
    }
    int l = min(dfn[x], dfn[y]);
    int r = max(dfn[x], dfn[y]);
    res += Tree.sum(l, r);
    res %= P;
    return res;
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    cin >> N >> M >> R >> P;
    Tree = Segtree(N);
    for (int i = 1; i <= N; i++)
        cin >> val[i];
    for (int i = 1; i < N; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs1(R, 1, -1);
    dfs2(R, R);
    for (int i = 1; i <= N; i++) {
        Tree.add(dfn[i], dfn[i], val[i]);
    }
    while (M--) {
        int op, x, y, z;
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> z;
            RoadAdd(x, y, z);
        }
        if (op == 2) {
            cin >> x >> y;
            cout << RoadSum(x, y) << endl;
        }
        if (op == 3) {
            cin >> x >> z;
            TrAdd(x, z);
        }
        if (op == 4) {
            cin >> x;
            cout << TrSum(x) << endl;
        }
    }
    return 0;
}

Segment Tree 洛谷测模板题 200ms。

/kel /kel /kel /kel /kel /kel /kel