社会送温暖

GitHub跳转原题关系图返回列表

树链剖分把路径拆成 O(log n) 段连续 dfn 区间;线段树懒标记把等差与公比 2 等比统一成「锚定两端的 2 的幂 + 一次函数」,任意模数 P 下都不求逆元。

OJ: roj

题目 ID: 1764

难度:提高+/省选-

标签:树链剖分线段树懒标记python

创建: 2026-10-07 23:31

更新: 2026-10-07 23:31

形式化题目

给出一棵 nn 个节点的树,每个节点带一个金币数 AiA_i。每次操作选择两个节点 u,vu, v,取出 uu 到 vv 的唯一简单路径,把路径上的节点按从 uu 走到 vv 的顺序编号为 1,2,…,L1, 2, \dots, L(LL 为路径长度即点数),然后执行五种操作之一:

  • op=1op = 1:第 ii 个点加上 a+(i−1)da + (i-1)d;
  • op=2op = 2:第 ii 个点加上 a⋅2 i−1a \cdot 2^{\,i-1};
  • op=3op = 3:第 ii 个点改为 a+(i−1)da + (i-1)d;
  • op=4op = 4:第 ii 个点改为 a⋅2 i−1a \cdot 2^{\,i-1};
  • op=5op = 5:询问路径上所有点金币数之和模 PP。

输出每个询问的答案。注意模数 PP 不必是质数,甚至可以是 11。

样例输入里 55 个点连成以 33 为中心的星形,按题面顺序执行如下:

操作 路径(u→vu \to v) 每个点受到的改动 结果
4 5 1 27096 5→3→15 \to 3 \to 1 第 1 个点 55 改 2709627096、第 2 个点 33 改 2⋅270962 \cdot 27096、第 3 个点 11 改 4⋅270964 \cdot 27096 5:27096, 3:24881, 1:204515{:}27096,\ 3{:}24881,\ 1{:}20451
4 2 3 17348 2→32 \to 3 22 改 1734817348、33 改 3473634736 2:17348, 3:54252{:}17348,\ 3{:}5425
3 1 2 8785 8918 1→3→21 \to 3 \to 2 11 改 87858785、33 改 8785+89188785+8918、22 改 8785+2⋅89188785+2 \cdot 8918 1:8785, 3:17703, 2:266211{:}8785,\ 3{:}17703,\ 2{:}26621
5 3 5 3→53 \to 5 询问 17703+27096=44799≡1548817703 + 27096 = 44799 \equiv 15488

表中数字均已模 2931129311。观察第三行:路径是 1→3→21 \to 3 \to 2,所以节点 11 是"第 1 个"、节点 33 是"第 2 个"、节点 22 是"第 3 个"——编号只由起点 uu 的方向决定,与树的根、与 u,vu,v 的祖孙关系都无关。

正解

思路

第一步:把路径变成区间。 一次操作要改一整条路径,而路径上的点分散在树上。用树链剖分:每条重链在 dfs 序(dfn)上连续,于是 u→vu \to v 的路径被拆成 O(log⁡n)O(\log n) 段连续 dfn 区间,每段还各自是一条重链上的竖直段。这样路径加/改就变成了 O(log⁡n)O(\log n) 次"区间加/改同一个函数"。

第二步:看清段内的函数形状。 设段是 dfn 区间 [l,r][l, r]。在一条重链上,dfn 随深度单调递增,而路径编号 ii 随深度单调变化,所以段内 ii 是位置 pp 的一次函数:

  • 从 uu 往上走到 LCA 的那一侧(uu 侧),深度越大编号越小,i(p)=i0+(r−p)i(p) = i_0 + (r - p);
  • 从 LCA 往下走到 vv 的那一侧(vv 侧),深度越大编号越大,i(p)=i0+(p−l)i(p) = i_0 + (p - l)。

其中 i0i_0 是锚点(uu 侧的右端点 rr、vv 侧的左端点 ll)处的编号。于是四种操作在段内都成了显式函数:

  • op=1,3op = 1, 3:值为 a+(i−1)da + (i-1)d,代入上式就是 pp 的一次函数 c0+c1pc_0 + c_1 p;
  • op=2,4op = 2, 4:值为 a⋅2 i−1=(a⋅2 i0−1)⋅2 ±(p−锚点)a \cdot 2^{\,i-1} = \big(a \cdot 2^{\,i_0 - 1}\big) \cdot 2^{\,\pm(p - \text{锚点})},是"常数乘 22 的位置次幂"。

第三步:难点在"任意模数"。 线段树要能对区间整体打懒标记。如果按常规做法把函数写成"系数 ×2p\times 2^{p}",那么把一个只覆盖半个区间的更新往下传时,系数要乘 2−k2^{-k} 才能换成子区间的坐标——22 的逆元在 PP 为偶数时根本不存在(PP 还可以是 11)。所以整个实现里不许出现任何除法或逆元。

关键观察:把指数锚定在区间两端,指数就永远非负。 把懒标记设计成

f(p)=A⋅2 p−l+B⋅2 r−p+c0+c1p(modP)f(p) = A \cdot 2^{\,p-l} + B \cdot 2^{\,r-p} + c_0 + c_1 p \pmod P

其中 l,rl, r 是当前节点自己的区间两端。2p−l2^{p-l} 与 2r−p2^{r-p} 的指数在区间内恒为 ⩾0\geqslant 0,只用预处理的 pow2[k] = 2^k mod P 就能算,不需要逆元;而 AA 与 BB 是两套独立的锚(一个锚左端、一个锚右端),一次更新用哪一套、往哪边锚,由该段的方向决定:

  • 段是 vv 侧(编号随 dfn 递增):A=a⋅2 i0−1A = a \cdot 2^{\,i_0 - 1},B=0B = 0;
  • 段是 uu 侧(编号随 dfn 递减):B=a⋅2 i0−1B = a \cdot 2^{\,i_0 - 1},A=0A = 0;
  • 等差情形只需 c0,c1c_0, c_1:左锚时 c0=a+(i0−l−1)d, c1=dc_0 = a + (i_0 - l - 1)d,\ c_1 = d;右锚时 c0=a+(i0+r−1)d, c1=−dc_0 = a + (i_0 + r - 1)d,\ c_1 = -d。

这个函数族对加法封闭,所以同一节点上多次更新可以直接把四个系数分别相加,懒标记不膨胀。

第四步:区间求和。 有了四个系数,整段的贡献是

∑p=lrf(p)=(A+B)(2 len−1)+c0⋅len+c1∑p=lrp(modP),len=r−l+1\sum_{p=l}^{r} f(p) = (A + B)\big(2^{\,len} - 1\big) + c_0 \cdot len + c_1 \sum_{p=l}^{r} p \pmod P, \quad len = r - l + 1

等比部分用了 ∑k=0len−12k=2len−1\sum_{k=0}^{len-1} 2^k = 2^{len} - 1,一次项部分用位置和公式/前缀和——两处都没有除法。

第五步:下传时把锚点平移。 节点 [l,r][l, r] 的标记要传给左孩子 [l,mid][l, mid]:左锚不变,右锚由 rr 变成 midmid,于是 B左=B⋅2 r−midB_{\text{左}} = B \cdot 2^{\,r-mid};传给右孩子 [mid+1,r][mid+1, r] 时对称地 A右=A⋅2 mid+1−lA_{\text{右}} = A \cdot 2^{\,mid+1-l}。指数同样非负。更新落到某个整段节点 [l′,r′][l', r'] 上时,也做一次同样的平移:把锚从查询区间两端挪到 l′,r′l', r' 上。

第六步:赋值与加法的复合。 懒标记带一个 hasSet 标志:若节点上挂的是"整体赋值 ff",此时再来一次"整体加 gg",效果等于"整体赋值 f+gf + g",所以直接把 gg 的系数并进标记、标志保持为赋值即可;若本来就是加法标记,再叠加法也只是系数相加。下传赋值标记时,两个孩子被直接覆盖(它们的旧标记作废)。

第七步:路径两侧和 LCA。 从 uu 往 LCA 跳的每一段都是 uu 侧(右锚),从 vv 往 LCA 跳的每一段都是 vv 侧(左锚),两边的编号公式分别是 dep[u]−dep[x]+1dep[u] - dep[x] + 1 和 dep[u]+dep[x]−2 dep[L]+1dep[u] + dep[x] - 2\,dep[L] + 1;LCA 自身属于两侧的交点,最后单独按 i=dep[u]−dep[L]+1i = dep[u] - dep[L] + 1 处理一次,避免重复。询问就是把同样的 O(log⁡n)O(\log n) 段区间和加起来。

边界。 n=1n = 1(没有边)、u=vu = v(路径只有一个点)、P=1P = 1(一切为 00)、PP 为偶数(22 不可逆)都必须能跑:前两个靠"LCA 单独处理 + 空段不操作"自然成立,后两个靠上面的"指数非负、全程不除法"保证。

代码

正式主解是 C++(main.cpp);main.py 是同一算法的 Python 短解法(自底向上的懒标记线段树,复杂度同阶)。

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 23:31
# update_at: 2026-10-07 23:31

import sys
from collections.abc import Iterator

type IntList = list[int]              # 下标 -> 整数,线段树 / 树链剖分 / 前缀量都用它
type Vec = list[list[int]]            # 邻接表:点 -> 邻居列表


def build_hld(adj: Vec, n: int) -> tuple[IntList, IntList, IntList, IntList, IntList]:
    """树链剖分,返回 (fa, dep, son, top, dfn),复杂度 O(n)。

    每条重链在 dfn 上连续,于是树上任意一条路径都能拆成 O(log n) 段连续 dfn 区间;
    段内「从 u 数第几个点」这个编号随 dfn 单调,正好是本线段树要处理的形状。
    """
    fa = [0] * (n + 1)
    dep = [0] * (n + 1)
    sz = [0] + [1] * n                # sz[0] = 0 当"没有孩子"的哨兵,其余每个点先算自己
    son = [0] * (n + 1)
    order = [1]                       # 边遍历边追加,天然得到 BFS 序
    for u in order:
        for v in adj[u]:
            if v != fa[u]:
                fa[v] = u
                dep[v] = dep[u] + 1
                order.append(v)
    for u in reversed(order):         # 逆 BFS 序 = 先儿子后父亲
        for v in adj[u]:
            if v != fa[u]:
                sz[u] += sz[v]
                if sz[v] > sz[son[u]]:
                    son[u] = v
    top = [0] * (n + 1)
    dfn = [0] * (n + 1)
    top[1] = 1
    cur = 0
    stk = [1]
    while stk:
        u = stk.pop()
        cur += 1
        dfn[u] = cur
        h = son[u]
        for v in adj[u]:              # 轻儿子先压栈、重儿子后压,于是重儿子先出栈
            if v != fa[u] and v != h:
                top[v] = v
                stk.append(v)
        if h:
            top[h] = top[u]
            stk.append(h)
    return fa, dep, son, top, dfn


def process(n: int, q: int, P: int, adj: Vec, init: IntList, data: Iterator[int]) -> IntList:
    """建树链剖分 + 线段树,顺序执行 q 条操作,返回所有询问的答案(已模 P)。

    线段树上的函数族 f(p) = A*2^(p-lv) + B*2^(rv-p) + C + D*p(lv/rv 是节点 v 的两端):
    等差部分就是 C + D*p;等比部分把系数锚在区间两端,指数永远非负,
    所以 P 为偶数(2 没有逆元)时照样成立。求和用 2^len-1 与位置和公式,全程不除法。
    """
    fa, dep, son, top, dfn = build_hld(adj, n)

    log = max(1, (n - 1).bit_length())    # size = 2^log ≥ n:叶下标 size+p-1 对应位置 p
    size = 1 << log
    m = 2 * size
    pow2 = [1 % P] * (size + 1)           # pow2[k] = 2^k mod P
    for i in range(1, size + 1):
        pow2[i] = pow2[i - 1] * 2 % P

    ln = [0] * m                          # ln[v]: 节点 v 覆盖的长度
    off = [0] * m                         # off[v]: v 的区间左端在 [0, size) 里的偏移
    ln[1] = size
    for v in range(1, size):
        half = ln[v] >> 1
        ln[v + v] = ln[v + v + 1] = half
        off[v + v] = off[v]
        off[v + v + 1] = off[v] + half
    glen = [0] * m                        # glen[v]: (2^ln[v] - 1) mod P,等比部分的系数
    lenm = [0] * m                        # lenm[v]: ln[v] mod P,常数部分的系数
    sump = [0] * m                        # sump[v]: 区间内位置之和 mod P,一次项系数
    for v in range(1, m):
        d = ln[v]
        glen[v] = (pow2[d] - 1) % P
        lenm[v] = d % P
        sump[v] = ((off[v] + 1 + off[v] + d) * d // 2) % P

    seg = [0] * m                         # 区间和
    tA = [0] * m                          # 懒标记:2^(p-lv) 的系数
    tB = [0] * m                          # 懒标记:2^(rv-p) 的系数
    tC = [0] * m                          # 懒标记:常数项
    tD = [0] * m                          # 懒标记:p 的系数
    isSet = bytearray(m)                  # 1 表示该标记是"整体赋值"而不是"加"
    for i in range(1, n + 1):             # 叶子上放初值
        seg[size + dfn[i] - 1] = init[i - 1] % P
    for v in range(size - 1, 0, -1):
        seg[v] = (seg[v + v] + seg[v + v + 1]) % P

    def push(v: int) -> None:
        """把 v 的懒标记下传:锚点从 v 的两端平移到两个孩子的两端。"""
        A, B, C, D = tA[v], tB[v], tC[v], tD[v]
        w = pow2[ln[v] >> 1]              # 半段长度:右孩子的左锚、左孩子的右锚各差它
        bl, ar = B * w % P, A * w % P
        for c, ca, cb in ((v + v, A, bl), (v + v + 1, ar, B)):
            if isSet[v]:
                seg[c] = ((ca + cb) * glen[c] + C * lenm[c] + D * sump[c]) % P
                tA[c] = ca
                tB[c] = cb
                tC[c] = C
                tD[c] = D
                isSet[c] = 1
            else:
                seg[c] = (seg[c] + (ca + cb) * glen[c] + C * lenm[c] + D * sump[c]) % P
                tA[c] = (tA[c] + ca) % P
                tB[c] = (tB[c] + cb) % P
                tC[c] = (tC[c] + C) % P
                tD[c] = (tD[c] + D) % P
        isSet[v] = 0
        tA[v] = tB[v] = tC[v] = tD[v] = 0

    def apply_node(v: int, A: int, B: int, C: int, D: int, st: int, l0: int, r0: int) -> None:
        """把以查询区间两端为锚的 (A, B) 平移到节点 v 自己的两端,再落到 v 上。"""
        av = A * pow2[off[v] - l0 + size] % P                 # 左锚从 ql 挪到 v 的左端
        bv = B * pow2[r0 - size - off[v] - ln[v]] % P         # 右锚从 qr 挪到 v 的右端
        if st:
            seg[v] = ((av + bv) * glen[v] + C * lenm[v] + D * sump[v]) % P
            tA[v] = av
            tB[v] = bv
            tC[v] = C
            tD[v] = D
            isSet[v] = 1
        else:
            seg[v] = (seg[v] + (av + bv) * glen[v] + C * lenm[v] + D * sump[v]) % P
            tA[v] = (tA[v] + av) % P
            tB[v] = (tB[v] + bv) % P
            tC[v] = (tC[v] + C) % P
            tD[v] = (tD[v] + D) % P

    def range_apply(l: int, r: int, A: int, B: int, C: int, D: int, st: int) -> None:
        """dfn 闭区间 [l, r] 上整体加(st=0)或整体改(st=1)这个函数。"""
        l += size - 1
        r += size                                       # 换成叶下标上的半开区间 [l, r)
        l0, r0 = l, r
        for i in range(log, 0, -1):                     # 先自顶向下把沿途标记推掉
            v = l >> i
            if v << i != l and (isSet[v] or tA[v] or tB[v] or tC[v] or tD[v]):
                push(v)
            if (r >> i) << i != r:
                v = (r - 1) >> i
                if isSet[v] or tA[v] or tB[v] or tC[v] or tD[v]:
                    push(v)
        while l < r:                                    # 覆盖区间的 O(log n) 个节点
            if l & 1:
                apply_node(l, A, B, C, D, st, l0, r0)
                l += 1
            if r & 1:
                r -= 1
                apply_node(r, A, B, C, D, st, l0, r0)
            l >>= 1
            r >>= 1
        l, r = l0, r0
        for i in range(1, log + 1):                     # 自底向上把沿途和重算
            v = l >> i
            if v << i != l:
                seg[v] = (seg[v + v] + seg[v + v + 1]) % P
            if (r >> i) << i != r:
                v = (r - 1) >> i
                seg[v] = (seg[v + v] + seg[v + v + 1]) % P

    def range_sum(l: int, r: int) -> int:
        """dfn 闭区间 [l, r] 上的金币和 mod P。"""
        l += size - 1
        r += size
        for i in range(log, 0, -1):
            v = l >> i
            if v << i != l and (isSet[v] or tA[v] or tB[v] or tC[v] or tD[v]):
                push(v)
            if (r >> i) << i != r:
                v = (r - 1) >> i
                if isSet[v] or tA[v] or tB[v] or tC[v] or tD[v]:
                    push(v)
        res = 0
        while l < r:
            if l & 1:
                res += seg[l]
                l += 1
            if r & 1:
                r -= 1
                res += seg[r]
            l >>= 1
            r >>= 1
        return res % P

    def lca(u: int, v: int) -> int:
        """轻重链跳法求最近公共祖先。"""
        while top[u] != top[v]:
            if dep[top[u]] < dep[top[v]]:
                u, v = v, u
            u = fa[top[u]]
        return u if dep[u] < dep[v] else v

    def seg_apply(l: int, r: int, idx: int, left: int, op: int, a: int, d: int) -> None:
        """段 [l, r] 上施加 op;idx 是锚点处的路径编号,left=1 表示编号随 dfn 递增。"""
        if op == 1 or op == 3:                          # 第 i 个点加/改成 a + (i-1)d
            if left:
                C = (a + (idx - l - 1) % P * d) % P     # i-1 = idx-1 + (p-l)
                D = d
            else:
                C = (a + (idx + r - 1) % P * d) % P     # i-1 = idx-1 + (r-p)
                D = (P - d) % P
            range_apply(l, r, 0, 0, C, D, op == 3)
        else:                                           # 第 i 个点加/改成 a*2^(i-1)
            base = a * pow2[idx - 1] % P                # 锚点处是 a*2^(idx-1)
            range_apply(l, r, base if left else 0, 0 if left else base, 0, 0, op == 4)

    def path_apply(u: int, v: int, op: int, a: int, d: int) -> None:
        """把 u 到 v 路径上的点按从 u 起的顺序编号,施加一次 op 操作。"""
        L = lca(u, v)
        du = dep[u]
        x = u
        while top[x] != top[L]:                         # u 侧:编号 = du-dep[x]+1,随 dfn 递减
            seg_apply(dfn[top[x]], dfn[x], du - dep[x] + 1, 0, op, a, d)
            x = fa[top[x]]
        if x != L:
            seg_apply(dfn[L] + 1, dfn[x], du - dep[x] + 1, 0, op, a, d)
        y = v
        while top[y] != top[L]:                         # v 侧:编号 = du+dep[y]-2dep[L]+1,递增
            seg_apply(dfn[top[y]], dfn[y], du + dep[top[y]] - 2 * dep[L] + 1, 1, op, a, d)
            y = fa[top[y]]
        if y != L:
            seg_apply(dfn[L] + 1, dfn[y], du - dep[L] + 2, 1, op, a, d)
        seg_apply(dfn[L], dfn[L], du - dep[L] + 1, 1, op, a, d)   # L 自己只算一次

    def path_sum(u: int, v: int) -> int:
        """u 到 v 路径上的金币和 mod P。"""
        L = lca(u, v)
        res = 0
        x = u
        while top[x] != top[L]:
            res += range_sum(dfn[top[x]], dfn[x])
            x = fa[top[x]]
        if x != L:
            res += range_sum(dfn[L] + 1, dfn[x])
        y = v
        while top[y] != top[L]:
            res += range_sum(dfn[top[y]], dfn[y])
            y = fa[top[y]]
        if y != L:
            res += range_sum(dfn[L] + 1, dfn[y])
        res += range_sum(dfn[L], dfn[L])
        return res % P

    ans: IntList = []
    for _ in range(q):
        op, u, v = next(data), next(data), next(data)
        if op == 5:
            ans.append(path_sum(u, v))
        elif op == 1 or op == 3:
            path_apply(u, v, op, next(data), next(data))
        else:
            path_apply(u, v, op, next(data), 0)
    return ans


def solve() -> None:
    """读入 + 调用 + 输出。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, q, P = next(data), next(data), next(data)

    adj: Vec = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v = next(data), next(data)
        adj[u].append(v)
        adj[v].append(u)
    init = [next(data) for _ in range(n)]      # A_1 .. A_n

    ans = process(n, q, P, adj, init, data)
    sys.stdout.write('\n'.join(map(str, ans)) + ('\n' if ans else ''))


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 23:31
 * update_at: 2026-10-07 23:31
 */
/*
 * 1764. 社会送温暖
 *
 * 题意:给一棵 n 个点的树,每个点有金币数 A_i。每次操作选定 u,v,
 *       把 u 到 v 路径上的点按「从 u 走到 v 的顺序」编号为 1,2,3,...:
 *         op=1 第 i 个点加 a+(i-1)d      op=2 第 i 个点加 a*2^(i-1)
 *         op=3 第 i 个点改为 a+(i-1)d    op=4 第 i 个点改为 a*2^(i-1)
 *         op=5 询问路径上金币和 mod P
 *       1<=n,q<=1e5,1<=P<=1e7(不必是质数),0<=A_i,a,d<=2^31。
 *
 * 做法:树链剖分把路径拆成 O(log n) 段连续 dfn 区间,每段内「路径编号」
 *       是关于 dfn 的一次函数(沿重链 dfn 单调,编号随之单调),于是每段
 *       加/改的值可写成 f(p)=A*2^(p-l)+B*2^(r-p)+c0+c1*p 的形式。
 *       线段树维护该函数族的懒标记:
 *         - 等差部分就是 c0+c1*p(线性,直接合并);
 *         - 等比部分把系数锚定在区间两端,指数只用非负的 2^k,
 *           从而 P 为偶数(2 不可逆)时也成立。
 *       求和时用 sum_{k=0}^{len-1}2^k = 2^len-1 与位置前缀和(避免除以 2)。
 *       复杂度 O((n+q) log^2 n)。
 *
 * 编译:/opt/homebrew/bin/g++-16 -O2 -std=c++17 main.cpp -o main
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 100005;

int n, q;
ll P;

/* ---------------- 邻接表 ---------------- */
int eHead[MAXN], eNext[2 * MAXN], eTo[2 * MAXN], eCnt;

inline void addEdge(int u, int v) {
    eTo[eCnt] = v;
    eNext[eCnt] = eHead[u];
    eHead[u] = eCnt++;
}

/* ---------------- 树链剖分 ---------------- */
int dep[MAXN], fa[MAXN], sz[MAXN], son[MAXN], top[MAXN], dfn[MAXN], rnk[MAXN];
ll initVal[MAXN], flatVal[MAXN];   // 点上的初值 / 按 dfn 展平后的初值
int bfsOrder[MAXN];

/* ---------------- 预处理 ---------------- */
ll pow2[MAXN + 2];      // pow2[k] = 2^k mod P
ll preSum[MAXN + 2];    // preSum[i] = (1+2+...+i) mod P

inline ll norm(ll x) { x %= P; if (x < 0) x += P; return x; }

/* ---------------- 线段树 ---------------- */
/*
 * 懒标记描述一个函数 f,对区间 [l,r] 内的位置 p:
 *     f(p) = tagA * 2^(p-l) + tagB * 2^(r-p) + tagC + tagD * p   (mod P)
 * hasSet=false:把 f 加到子区间上;hasSet=true:把子区间整体赋值为 f。
 */
ll segSum[4 * MAXN];
ll tagA[4 * MAXN], tagB[4 * MAXN], tagC[4 * MAXN], tagD[4 * MAXN];
bool hasSet[4 * MAXN];

// 函数 f 在 [l,r] 上的和
inline ll funcSum(ll A, ll B, ll C, ll D, int l, int r) {
    int len = r - l + 1;
    ll g = norm(pow2[len] - 1);                 // sum_{k=0}^{len-1} 2^k
    ll res = (norm(A) * g + norm(B) * g) % P;
    res = (res + norm(C) * (len % P)) % P;
    ll spos = norm(preSum[r] - preSum[l - 1]);  // sum_{p=l}^{r} p
    res = (res + norm(D) * spos) % P;
    return res;
}

inline void applyAdd(int o, int l, int r, ll A, ll B, ll C, ll D) {
    A = norm(A); B = norm(B); C = norm(C); D = norm(D);
    segSum[o] = (segSum[o] + funcSum(A, B, C, D, l, r)) % P;
    tagA[o] = (tagA[o] + A) % P;
    tagB[o] = (tagB[o] + B) % P;
    tagC[o] = (tagC[o] + C) % P;
    tagD[o] = (tagD[o] + D) % P;
    // 若原本是「赋值 f」,再「加 g」等价于「赋值 f+g」,hasSet 保持 true
}

inline void applySet(int o, int l, int r, ll A, ll B, ll C, ll D) {
    A = norm(A); B = norm(B); C = norm(C); D = norm(D);
    segSum[o] = funcSum(A, B, C, D, l, r);
    tagA[o] = A; tagB[o] = B; tagC[o] = C; tagD[o] = D;
    hasSet[o] = true;
}

inline void pushDown(int o, int l, int r) {
    if (!hasSet[o] && tagA[o] == 0 && tagB[o] == 0 && tagC[o] == 0 && tagD[o] == 0)
        return;
    int mid = (l + r) >> 1;
    int lenL = mid - l + 1, lenR = r - mid;
    ll A = tagA[o], B = tagB[o], C = tagC[o], D = tagD[o];
    // 左子 [l,mid]:左端仍是 l,右端由 r 变成 mid,指数少 lenR
    ll Al = A, Bl = B * pow2[lenR] % P;
    // 右子 [mid+1,r]:右端仍是 r,左端由 l 变成 mid+1,指数少 lenL
    ll Ar = A * pow2[lenL] % P, Br = B;
    if (hasSet[o]) {
        applySet(o << 1, l, mid, Al, Bl, C, D);
        applySet(o << 1 | 1, mid + 1, r, Ar, Br, C, D);
        hasSet[o] = false;
    } else {
        applyAdd(o << 1, l, mid, Al, Bl, C, D);
        applyAdd(o << 1 | 1, mid + 1, r, Ar, Br, C, D);
    }
    tagA[o] = tagB[o] = tagC[o] = tagD[o] = 0;
}

void build(int o, int l, int r) {
    if (l == r) { segSum[o] = flatVal[l] % P; return; }
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    segSum[o] = (segSum[o << 1] + segSum[o << 1 | 1]) % P;
}

// (A,B) 以查询区间两端为锚:A 锚在 p=ql,B 锚在 p=qr
void updateAdd(int o, int l, int r, int ql, int qr, ll A, ll B, ll C, ll D) {
    if (ql <= l && r <= qr) {
        applyAdd(o, l, r, A * pow2[l - ql] % P, B * pow2[qr - r] % P, C, D);
        return;
    }
    pushDown(o, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) updateAdd(o << 1, l, mid, ql, qr, A, B, C, D);
    if (qr > mid) updateAdd(o << 1 | 1, mid + 1, r, ql, qr, A, B, C, D);
    segSum[o] = (segSum[o << 1] + segSum[o << 1 | 1]) % P;
}

void updateSet(int o, int l, int r, int ql, int qr, ll A, ll B, ll C, ll D) {
    if (ql <= l && r <= qr) {
        applySet(o, l, r, A * pow2[l - ql] % P, B * pow2[qr - r] % P, C, D);
        return;
    }
    pushDown(o, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) updateSet(o << 1, l, mid, ql, qr, A, B, C, D);
    if (qr > mid) updateSet(o << 1 | 1, mid + 1, r, ql, qr, A, B, C, D);
    segSum[o] = (segSum[o << 1] + segSum[o << 1 | 1]) % P;
}

ll querySum(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return segSum[o];
    pushDown(o, l, r);
    int mid = (l + r) >> 1;
    ll res = 0;
    if (ql <= mid) res += querySum(o << 1, l, mid, ql, qr);
    if (qr > mid) res += querySum(o << 1 | 1, mid + 1, r, ql, qr);
    return res % P;
}

/* ---------------- 单段操作 ---------------- */
/*
 * 段 [l,r](dfn 连续)。anchorIdx = 锚点位置的「路径编号」:
 *   leftAnchored=true :锚点在最左端 p=l,编号随 p 递增(i = anchorIdx + p - l),u=... 的 v 侧;
 *   leftAnchored=false:锚点在最右端 p=r,编号随 p 递减(i = anchorIdx + r - p),u 侧。
 */
inline void applySeg(int l, int r, int anchorIdx, bool leftAnchored, int op, ll a, ll d) {
    a = norm(a); d = norm(d);
    ll A = 0, B = 0, C = 0, D = 0;
    if (op == 1 || op == 3) {
        // 值为 a + (i-1)d,是 p 的一次函数
        if (leftAnchored) {
            // i-1 = anchorIdx-1 + (p-l)  =>  f(p) = [a + (anchorIdx-l-1)d] + d*p
            ll k = norm((ll)anchorIdx - l - 1);
            C = (a + k * d) % P;
            D = d;
        } else {
            // i-1 = anchorIdx-1 + (r-p)  =>  f(p) = [a + (anchorIdx+r-1)d] - d*p
            ll k = norm((ll)anchorIdx + r - 1);
            C = (a + k * d) % P;
            D = norm(P - d);
        }
    } else {
        // 值为 a*2^(i-1),锚定在区间端点,指数恒非负
        ll base = a * pow2[anchorIdx - 1] % P;
        if (leftAnchored) A = base;
        else              B = base;
    }
    if (op == 1 || op == 2) updateAdd(1, 1, n, l, r, A, B, C, D);
    else                    updateSet(1, 1, n, l, r, A, B, C, D);
}

inline int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

/* ---------------- 路径操作 ---------------- */
void pathUpdate(int u, int v, int op, ll a, ll d) {
    int U0 = u;
    int L = lca(u, v);
    // u 侧:编号 i(x) = dep[U0]-dep[x]+1,沿 dfn 递增编号递减 => 右端锚定
    int x = u;
    while (top[x] != top[L]) {
        applySeg(dfn[top[x]], dfn[x], dep[U0] - dep[x] + 1, false, op, a, d);
        x = fa[top[x]];
    }
    if (x != L) {
        // 此时 x 与 L 同链,[dfn[L]+1, dfn[x]] 是去掉 L 的剩余部分
        applySeg(dfn[L] + 1, dfn[x], dep[U0] - dep[x] + 1, false, op, a, d);
    }
    // v 侧:编号 i(x) = dep[U0]+dep[x]-2dep[L]+1,沿 dfn 递增编号递增 => 左端锚定
    int y = v;
    while (top[y] != top[L]) {
        applySeg(dfn[top[y]], dfn[y], dep[U0] + dep[top[y]] - 2 * dep[L] + 1, true, op, a, d);
        y = fa[top[y]];
    }
    if (y != L) {
        applySeg(dfn[L] + 1, dfn[y], dep[U0] - dep[L] + 2, true, op, a, d);
    }
    // L 本身
    applySeg(dfn[L], dfn[L], dep[U0] - dep[L] + 1, true, op, a, d);
}

ll pathQuery(int u, int v) {
    int U0 = u;
    int L = lca(u, v);
    ll res = 0;
    int x = u;
    while (top[x] != top[L]) {
        res += querySum(1, 1, n, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if (x != L) res += querySum(1, 1, n, dfn[L] + 1, dfn[x]);
    int y = v;
    while (top[y] != top[L]) {
        res += querySum(1, 1, n, dfn[top[y]], dfn[y]);
        y = fa[top[y]];
    }
    if (y != L) res += querySum(1, 1, n, dfn[L] + 1, dfn[y]);
    res += querySum(1, 1, n, dfn[L], dfn[L]);
    return res % P;
}

/* ---------------- 快读 ---------------- */
static char inBuf[1 << 25];
static size_t inLen = 0, inPos = 0;

inline ll readLL() {
    if (inPos >= inLen) { inLen = fread(inBuf, 1, sizeof(inBuf), stdin); inPos = 0; }
    while (inPos < inLen && (inBuf[inPos] < '0' || inBuf[inPos] > '9')) inPos++;
    ll x = 0;
    while (inPos < inLen && inBuf[inPos] >= '0' && inBuf[inPos] <= '9')
        x = x * 10 + (inBuf[inPos++] - '0');
    return x;
}
inline int readInt() { return (int)readLL(); }

int main() {
    n = readInt(); q = readInt(); P = readLL();
    memset(eHead, -1, sizeof(int) * (n + 1));
    eCnt = 0;
    for (int i = 0; i < n - 1; i++) {
        int u = readInt(), v = readInt();
        addEdge(u, v); addEdge(v, u);
    }
    for (int i = 1; i <= n; i++) initVal[i] = readLL();

    /* ---- BFS 求 fa / dep / 层次序 ---- */
    int qh = 0, qt = 0;
    bfsOrder[qt++] = 1; fa[1] = 0; dep[1] = 0;
    while (qh < qt) {
        int u = bfsOrder[qh++];
        for (int e = eHead[u]; e != -1; e = eNext[e]) {
            int v = eTo[e];
            if (v == fa[u]) continue;
            fa[v] = u; dep[v] = dep[u] + 1; bfsOrder[qt++] = v;
        }
    }
    /* ---- 逆序求 sz / 重儿子 ---- */
    for (int i = n; i >= 1; i--) {
        int u = bfsOrder[i - 1];
        sz[u] = 1; son[u] = 0;
        for (int e = eHead[u]; e != -1; e = eNext[e]) {
            int v = eTo[e];
            if (v == fa[u]) continue;
            sz[u] += sz[v];
            if (son[u] == 0 || sz[v] > sz[son[u]]) son[u] = v;
        }
    }
    /* ---- 分配 dfn:用栈让每条重链的 dfn 连续 ---- */
    {
        static int stk[MAXN];
        int sp = 0;
        stk[sp++] = 1; top[1] = 1;
        int cur = 0;
        while (sp) {
            int u = stk[--sp];
            dfn[u] = ++cur; rnk[cur] = u;
            for (int e = eHead[u]; e != -1; e = eNext[e]) {
                int v = eTo[e];
                if (v == fa[u] || v == son[u]) continue;
                top[v] = v; stk[sp++] = v;
            }
            if (son[u]) { top[son[u]] = top[u]; stk[sp++] = son[u]; }
        }
    }
    for (int i = 1; i <= n; i++) flatVal[dfn[i]] = initVal[i] % P;

    /* ---- 2 的幂 / 位置前缀和 ---- */
    pow2[0] = 1 % P;
    for (int i = 1; i <= n + 1; i++) pow2[i] = pow2[i - 1] * 2 % P;
    preSum[0] = 0;
    for (int i = 1; i <= n + 1; i++) preSum[i] = (preSum[i - 1] + i) % P;

    build(1, 1, n);

    for (int i = 0; i < q; i++) {
        int op = readInt(), u = readInt(), v = readInt();
        if (op == 5) {
            printf("%lld\n", pathQuery(u, v));
        } else if (op == 1 || op == 3) {
            ll a = readLL(), d = readLL();
            pathUpdate(u, v, op, a, d);
        } else {
            ll a = readLL();
            pathUpdate(u, v, op, a, 0);
        }
    }
    return 0;
}

复杂度

树链剖分 O(n)O(n);每次操作拆成 O(log⁡n)O(\log n) 段,每段一次 O(log⁡n)O(\log n) 的线段树操作,故单次 O(log⁡2n)O(\log^2 n),总计时间 O((n+q)log⁡2n)O\big((n + q)\log^2 n\big),空间 O(n)O(n)(线段树 4n4n 个节点,每个节点 5 个 ll 与 1 个 bool)。

本题 n,q⩽105n, q \leqslant 10^5、P⩽107P \leqslant 10^7、Ai,a,d⩽231A_i, a, d \leqslant 2^{31}。本地实测:C++(-O2)最大测试点 0.290.29 s、峰值约 2525 MB;Python 短解法最慢的完全二叉树点约 8.78.7 s、其余点 0.02∼6.20.02 \sim 6.2 s,算法与 C++ 同阶,只是常数大。

总结

本题把两种"看起来不搭"的东西拼在一起:树链剖分负责把路径变成 O(log⁡n)O(\log n) 段区间,带函数懒标记的线段树负责在这些区间上做加/改与求和。真正值得记住的是懒标记的设计:

  1. 区间内的加/改值是关于位置的一次函数或 22 的位置次幂,所以一次更新只需 4 个系数 (A,B,c0,c1)(A, B, c_0, c_1) 就能完整描述;
  2. 等比部分把系数锚定在区间两端,指数恒非负,于是模数 PP 任意(可为偶数、可为 11)都不需要 22 的逆元;代价是下传时要按半段长度乘一次 22 的幂来平移锚点;
  3. 等差部分求和要用位置和(前缀和或公式),否则会掉进"除以 22"的坑——PP 为偶数时同样不成立;
  4. 赋值与加法能共存,是因为"赋值 ff 后再加 gg"仍是同族的函数,只需把系数合并。

容易写错的点:路径两侧的编号方向相反(一侧右锚、一侧左锚)、LCA 只能算一次、以及更新落到线段树某个节点上时锚点必须从"查询区间两端"平移到"该节点两端"。

关于本题材料:题面来自网络重建,仓库里的测试数据由 data.py + std.cpp 自造(10 个点,覆盖样例、n=1n=1 与 P=1P=1 的退化、PP 为偶合数、链 / 星 / 完全二叉树 / 随机树、值域顶格 2312^{31})。我另外写了一份独立暴力(逐条路径直接模拟)与 std.cpp 对拍,两者一致,因此本题的题面语义与数据没有发现偏差;但出题意图仍可能与官方原题有出入,引用时请注意。