思路与算法

树链剖分把有向路径拆为区间，线段树懒标记同时保存等差首项与公差、左端锚定的gL·2^(i-l)、右端锚定的gR·2^(r-i)。区间和用等差和及(2^len-1)公式。覆盖清旧标记，添加累加；下推移动首项并乘2的幂，按路径方向和偏移定位各段。

正确性说明

三种基函数对平移和加法封闭，所以下推后每个子段的逐点增量与父标记相同。覆盖与添加的组合按时间顺序保持不变。树链段按原路径次序偏移，故等差与倍增项在链边界连续；查询求和就是各点最终温暖值之和。

复杂度

预处理2幂、重链和建树O(N)，每次路径操作O(log²N)，总O(N+Qlog²N)时间，O(N)空间；所有初始化计入。

易错点

模数可为1及偶合数，不使用2的逆元。反向等差公差变号，倍增改右端锚定。覆盖须先清除全部旧标签；取模规范化负数，乘积用64位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct HLD {
    int n;
    vector<vector<int>> g;
    vector<int> p, dep, sz, heavy, top, id, rev, ord;
    HLD(int n) : n(n), g(n), p(n, -1), dep(n), sz(n, 1), heavy(n, -1), top(n), id(n), rev(n) {
    }
    void build() {
        ord = {0};
        for (size_t i = 0; i < ord.size(); i++) {
            int u = ord[i];
            for (int v : g[u])
                if (v != p[u]) {
                    p[v] = u;
                    dep[v] = dep[u] + 1;
                    ord.push_back(v);
                }
        }
        for (int i = n - 1; i > 0; i--) {
            int u = ord[i], v = p[u];
            sz[v] += sz[u];
            if (heavy[v] < 0 || sz[u] > sz[heavy[v]])
                heavy[v] = u;
        }
        int timer = 0;
        vector<pair<int, int>> st(1, {0, 0});
        while (!st.empty()) {
            auto x = st.back();
            st.pop_back();
            for (int u = x.first; u >= 0; u = heavy[u]) {
                top[u] = x.second;
                id[u] = timer;
                rev[timer++] = u;
                for (int v : g[u])
                    if (v != p[u] && v != heavy[u])
                        st.push_back({v, v});
            }
        }
    }
    vector<array<int, 3>> path(int a, int b) {
        vector<array<int, 3>> L, R;
        while (top[a] != top[b]) {
            if (dep[top[a]] >= dep[top[b]]) {
                L.push_back({id[top[a]], id[a], 0});
                a = p[top[a]];
            } else {
                R.push_back({id[top[b]], id[b], 1});
                b = p[top[b]];
            }
        }
        if (dep[a] >= dep[b])
            L.push_back({id[b], id[a], 0});
        else
            L.push_back({id[a], id[b], 1});
        reverse(R.begin(), R.end());
        L.insert(L.end(), R.begin(), R.end());
        return L;
    }
};
struct Seg {
    int n;
    long long P;
    vector<long long> sum, A, D, L, R, pow2;
    vector<int> reset;
    Seg(vector<long long> &a, long long p)
        : n(a.size()), P(p), sum(4 * n), A(4 * n), D(4 * n), L(4 * n), R(4 * n), pow2(n + 1),
          reset(4 * n) {
        pow2[0] = 1 % P;
        for (int i = 1; i <= n; i++)
            pow2[i] = pow2[i - 1] * 2 % P;
        build(1, 0, n - 1, a);
    }
    long long norm(long long x) {
        return (x % P + P) % P;
    }
    void build(int v, int l, int r, vector<long long> &a) {
        if (l == r) {
            sum[v] = a[l] % P;
            return;
        }
        int m = (l + r) / 2;
        build(v * 2, l, m, a);
        build(v * 2 + 1, m + 1, r, a);
        sum[v] = (sum[v * 2] + sum[v * 2 + 1]) % P;
    }
    void apply(int v, int l, int r, long long a, long long d, long long x, long long y,
               bool clear) {
        if (clear) {
            sum[v] = A[v] = D[v] = L[v] = R[v] = 0;
            reset[v] = 1;
        }
        long long len = r - l + 1;
        sum[v] = norm(sum[v] + a * len + d * (len * (len - 1) / 2) % P +
                      (x + y) * norm(pow2[len] - 1) % P);
        A[v] = norm(A[v] + a);
        D[v] = norm(D[v] + d);
        L[v] = norm(L[v] + x);
        R[v] = norm(R[v] + y);
    }
    void push(int v, int l, int r) {
        if (l == r)
            return;
        int m = (l + r) / 2;
        apply(v * 2, l, m, A[v], D[v], L[v], R[v] * pow2[r - m] % P, reset[v]);
        apply(v * 2 + 1, m + 1, r, norm(A[v] + D[v] * (m + 1 - l)), D[v],
              L[v] * pow2[m + 1 - l] % P, R[v], reset[v]);
        A[v] = D[v] = L[v] = R[v] = 0;
        reset[v] = 0;
    }
    void update(int v, int l, int r, int ql, int qr, long long a, long long d, long long x,
                long long y, bool clear) {
        if (ql <= l && r <= qr) {
            apply(v, l, r, norm(a + d * (l - ql)), d, x * pow2[l - ql] % P, y * pow2[qr - r] % P,
                  clear);
            return;
        }
        push(v, l, r);
        int m = (l + r) / 2;
        if (ql <= m)
            update(v * 2, l, m, ql, qr, a, d, x, y, clear);
        if (qr > m)
            update(v * 2 + 1, m + 1, r, ql, qr, a, d, x, y, clear);
        sum[v] = (sum[v * 2] + sum[v * 2 + 1]) % P;
    }
    long long query(int v, int l, int r, int a, int b) {
        if (a <= l && r <= b)
            return sum[v];
        push(v, l, r);
        int m = (l + r) / 2;
        long long z = 0;
        if (a <= m)
            z += query(v * 2, l, m, a, b);
        if (b > m)
            z += query(v * 2 + 1, m + 1, r, a, b);
        return z % P;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    long long P;
    cin >> n >> q >> P;
    HLD h(n);
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        h.g[--a].push_back(--b);
        h.g[b].push_back(a);
    }
    h.build();
    vector<long long> a(n);
    for (int u = 0; u < n; u++) {
        long long x;
        cin >> x;
        a[h.id[u]] = x;
    }
    Seg s(a, P);
    while (q--) {
        int op, u, v;
        cin >> op >> u >> v;
        auto path = h.path(--u, --v);
        if (op == 5) {
            long long ans = 0;
            for (auto t : path)
                ans = (ans + s.query(1, 0, n - 1, t[0], t[1])) % P;
            cout << ans << '\n';
            continue;
        }
        long long a, d = 0;
        cin >> a;
        if (op == 1 || op == 3)
            cin >> d;
        a %= P;
        d %= P;
        int off = 0;
        for (auto t : path) {
            int l = t[0], r = t[1], len = r - l + 1;
            long long aa = 0, dd = 0, x = 0, y = 0;
            if (op == 1 || op == 3) {
                aa = s.norm(a + d * (off + (t[2] ? 0 : len - 1)));
                dd = t[2] ? d : s.norm(-d);
            } else if (t[2])
                x = a * s.pow2[off] % P;
            else
                y = a * s.pow2[off] % P;
            s.update(1, 0, n - 1, l, r, aa, dd, x, y, op >= 3);
            off += len;
        }
    }
}