树链剖分把路径拆成 O(log n) 段连续 dfn 区间;线段树懒标记把等差与公比 2 等比统一成「锚定两端的 2 的幂 + 一次函数」,任意模数 P 下都不求逆元。
OJ: roj
题目 ID: 1764
难度:提高+/省选-
标签:树链剖分线段树懒标记python
创建: 2026-10-07 23:31
更新: 2026-10-07 23:31
形式化题目
给出一棵
:第 个点加上 ; :第 个点加上 ; :第 个点改为 ; :第 个点改为 ; :询问路径上所有点金币数之和模 。
输出每个询问的答案。注意模数
样例输入里
| 操作 | 路径( |
每个点受到的改动 | 结果 |
|---|---|---|---|
4 5 1 27096 |
第 1 个点 |
||
4 2 3 17348 |
|||
3 1 2 8785 8918 |
|||
5 3 5 |
询问 |
表中数字均已模
正解
思路
第一步:把路径变成区间。 一次操作要改一整条路径,而路径上的点分散在树上。用树链剖分:每条重链在 dfs 序(dfn)上连续,于是
第二步:看清段内的函数形状。 设段是 dfn 区间
- 从
往上走到 LCA 的那一侧( 侧),深度越大编号越小, ; - 从 LCA 往下走到
的那一侧( 侧),深度越大编号越大, 。
其中
:值为 ,代入上式就是 的一次函数 ; :值为 ,是"常数乘 的位置次幂"。
第三步:难点在"任意模数"。 线段树要能对区间整体打懒标记。如果按常规做法把函数写成"系数
关键观察:把指数锚定在区间两端,指数就永远非负。 把懒标记设计成
其中 pow2[k] = 2^k mod P 就能算,不需要逆元;而
- 段是
侧(编号随 dfn 递增): , ; - 段是
侧(编号随 dfn 递减): , ; - 等差情形只需
:左锚时 ;右锚时 。
这个函数族对加法封闭,所以同一节点上多次更新可以直接把四个系数分别相加,懒标记不膨胀。
第四步:区间求和。 有了四个系数,整段的贡献是
等比部分用了
第五步:下传时把锚点平移。 节点
第六步:赋值与加法的复合。 懒标记带一个 hasSet 标志:若节点上挂的是"整体赋值
第七步:路径两侧和 LCA。 从
边界。
代码
正式主解是 C++(main.cpp);main.py 是同一算法的 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()/**
* 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;
}复杂度
树链剖分 ll 与 1 个 bool)。
本题 -O2)最大测试点
总结
本题把两种"看起来不搭"的东西拼在一起:树链剖分负责把路径变成
- 区间内的加/改值是关于位置的一次函数或
的位置次幂,所以一次更新只需 4 个系数 就能完整描述; - 等比部分把系数锚定在区间两端,指数恒非负,于是模数
任意(可为偶数、可为 )都不需要 的逆元;代价是下传时要按半段长度乘一次 的幂来平移锚点; - 等差部分求和要用位置和(前缀和或公式),否则会掉进"除以
"的坑—— 为偶数时同样不成立; - 赋值与加法能共存,是因为"赋值
后再加 "仍是同族的函数,只需把系数合并。
容易写错的点:路径两侧的编号方向相反(一侧右锚、一侧左锚)、LCA 只能算一次、以及更新落到线段树某个节点上时锚点必须从"查询区间两端"平移到"该节点两端"。
关于本题材料:题面来自网络重建,仓库里的测试数据由 data.py + std.cpp 自造(10 个点,覆盖样例、std.cpp 对拍,两者一致,因此本题的题面语义与数据没有发现偏差;但出题意图仍可能与官方原题有出入,引用时请注意。