P3384 【模板】重链剖分 / 树链剖分 · 习题解析

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P3384，日期见页头。两边不一致时信原站。

题目描述

如题，已知一棵包含 N 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

1 x y z，表示将树从 x 到 y 结点最短路径上所有节点的值都加上 z。
2 x y，表示求树从 x 到 y 结点最短路径上所有节点的值之和。
3 x z，表示将以 x 为根节点的子树内所有节点值都加上 z。
4 x，表示求以 x 为根节点的子树内所有节点值之和。

输入格式

第一行包含 4 个正整数 N, M, R, P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。

接下来一行包含 N 个非负整数，分别依次表示各个节点上初始的数值。

接下来 N−1 行每行包含两个整数 x, y，表示点 x 和点 y 之间连有一条边（保证无环且连通）。

接下来 M 行每行包含若干个正整数，每行表示一个操作。

输出格式

输出包含若干行，分别依次表示每个操作 2 或操作 4 所得的结果（对 P 取模）。

数据规模

对于 30% 的数据：1 ≤ N ≤ 10，1 ≤ M ≤ 10；

对于 70% 的数据：1 ≤ N ≤ 10³，1 ≤ M ≤ 10³；

对于 100% 的数据：1 ≤ N ≤ 10⁵，1 ≤ M ≤ 10⁵，1 ≤ R ≤ N，1 ≤ P ≤ 2³⁰。所有输入的数均在 int 范围内。

时限 1 秒，内存 131072 KB（128 MiB）。

输入输出样例

输入

输出

2
21

★ 样例说明里的两张图（转录自原站）：树的结构，以及五个操作分别在做什么。

P3384 样例的树

P3384 样例的五个操作

⚠ 注意第一行第三个数是 2 —— 这棵树的根是 2 号点，不是 1 号点。

1★★★ 剖分那一半，正文已经写完了 —— 而这道题会咬人的四处，一处都不在剖分里

★★ 先说清楚这一页在讲什么

这就是第 53 章正文那道题的原题。两趟遍历、跳链、 siz / son / top / dfn、五个「剖分本身写错」的版本、「重儿子挑错答案照样对、坏的只有复杂度」—— 那些全在正文里，这一页一个字都不重复。

⇒ 这一页只管剩下那一半：把题面第一行那四个数、和一句「所有输出对 P 取模」当真。四处关卡，按被踩到的顺序排：

	关卡	一句话
①	根是 `R`，不是 1	题面第一行第三个数。⚠ 而它只毁掉一半的输出
②	建线段树时要按 `rnk` 翻译	剖分做的事只有「换一个编号顺序」，建树那一步漏了翻译，初值就全站错位
③	取模的 `P` 是输入给的	而且只在输出取一次模会把 `long long` 撑爆 —— ⚠ 但对拍永远抓不到
④	`long long`	`1 ≤ P ≤ 2³⁰`，而线段树里那一句是 `v % MOD * len`

★ 而这四条里有两条，官方样例自己就挡得住 —— 第 ④ 步那张表有实测。

2第一版：照题面一句一句做

brute.cpp✗ 第一版（也是对拍的标准答案）：路径一个点一个点爬，子树整棵遍历

genBig.cpp★ 顶格生成器：rand / chain / star / 梳子

p3384Read.cpp★ 对照：只把 3.0 MB 输入读进来，一个操作都不做

★★★ 顶格 N = M = 10⁵（时限 1 秒）—— 顶格随机上，暴力比正解还快

顶格形状	✗ 暴力	★ 正解
`star`（菊花）	★ 0.03 秒	0.07 秒
`rand`（随机树）	★ 0.04 秒	0.13 秒
`comb`（梳子）	9.70 秒	0.10 秒
`chain`（链）	⚠ 22.39 秒	0.07 秒

（本机 · A 机 WSL2 · nproc 12 · 2026-09-13 · 独占 · 每格 3 次取中位数；只读入那一份 0.01 秒，四种形状都一样。）

⇒ ★★★ 顶格随机那一档，暴力比正解快 3.25 倍 —— 顺手造一组 n = m = 10⁵ 的随机树跑一遍，你会得出「这题暴力就能过」。 ⇒ 这是「顶格 ≠ 最坏」在这一章题单里的第一次，而后面两道题上它还要再中两次。

★ 原因一句话：随机树上两点之间平均只有 O(log n) 个点，而链上一条路径就是 n 个点 —— 同样的 n，差 560 倍（0.04 → 22.39）。

⚠⚠ 那 22.39 秒没写成断言 —— 跑一次就要 22 秒，而闸门本来就要跑半小时（和第 52 章 P3258 那两个 412 秒 / 39.89 秒同一个处理办法）。闸门里钉的是三条更便宜、也更说明问题的： ① O(nm) 的签名 —— 链上 n = m 从 8000 翻到 32000（×4）时间该 ×16，实测 120 → 1855 毫秒（15.5 倍）； ② 同样 n = m = 32000，链比随机树慢两个数量级（独占 1855 vs 17 毫秒 = 109 倍）； ③ 顶格随机那一档暴力比正解快。 ⚠ 而第 ② 条闸门里只钉「≥ 20 倍」，不是 109 —— 全量那一趟是 12 路并行，随机树那一格从 17 毫秒涨到 53，比值当场掉到 36 倍（第一版钉 50，翻红）。 ⇒ 秒表断言要同时过两关：余量够大＋不是单次测量，而「余量够大」得按有负载的时候算。 ★ 而正文第 ④ 步按 n = m ≤ 16000 外推说「约 21 秒」—— 实测 22.39，低估 6% （对照 P3258 那次低估 2.2 倍：那道题的暴力每秒处理的步数自己在随规模下降，这一份没有）。

3正解：把路径砍成 O(log n) 段连续区间

fast.cpp★ 正解：树链剖分＋线段树（区间加 / 区间求和）

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

// 树链剖分（重链剖分）+ 线段树 —— 正解
//
// 输入输出和 brute.cpp 完全一样，慢的那一层被换掉了：
//   暴力：一条路径一个点一个点爬，最坏 O(n)
//   这里：一条路径被拆成 O(log n) 段**连续区间**，每段丢给线段树 O(log n)
//   ⇒ 一次操作 O(log²n)。
//
// ============ 两趟遍历分别在算什么 ============
//
//   第一趟：fa / dep / siz / son
//     son[u] = u 的**重儿子** = 子树最大的那个儿子。
//     ⚠ **并列时挑谁不影响正确性**（挑谁都还是一条合法的重链剖分），
//       但它影响 dfn 的具体样子 —— 而动画那份 TS 要和这里**逐字节一致**，
//       所以两边都得是同一条规则：倒着扫 BFS 序、严格大于才换 ⇒ **编号靠后的那个赢**。
//
//   第二趟：top / dfn
//     **重儿子优先**地编号 ⇒ 一条重链上的 dfn 是**连续的一段**。
//     top[u] = u 所在重链最顶上那个点。
//
// ⇒ 于是两件事同时成立：
//     子树 = 区间 [dfn[u], dfn[u] + siz[u] - 1]      ← 任何 DFS 序都白送这一条
//     路径 = O(log n) 段区间                          ← 这一条只有「重儿子优先」才有
//
// ★ 为什么是 log：从 u 往上走一条**轻边**，子树大小至少翻倍
//   （轻儿子的子树 < 父亲子树的一半，否则它就该是重儿子）。
//   n 最多翻 log2(n) 次 ⇒ 根到任意点的轻边不超过 log2(n) 条 ⇒ 最多跳 log2(n)+1 条链。
//   ⇒ 这句话是**可以实测**的，见 count.cpp 那张「链 / 菊花 / 随机树」的表。
//
// ⚠ 两趟遍历都写成**非递归**：最坏形状就是一条 10⁵ 个点的链，
//   递归必爆栈（第 30 章实测：本机 8 MB 栈，DFS 到 285380 层就段错误）。

#include <bits/stdc++.h>
using namespace std;

static int n, m, root;
static long long MOD;
static vector<int> g[100005];
static long long w[100005];
static int fa[100005], dep[100005], siz[100005], son[100005];
static int top_[100005], dfn[100005], rnk[100005], bfsOrder[100005], cnt;

/* ---------- 线段树：区间加 + 区间求和（第 39 章那一套，这里不重讲） ---------- */
static long long sum[400005], lz[400005];
static void pull(int p) { sum[p] = (sum[p << 1] + sum[p << 1 | 1]) % MOD; }
static void apply_(int p, int len, long long v) {
    sum[p] = (sum[p] + v % MOD * len) % MOD;
    lz[p] = (lz[p] + v) % MOD;
}
static void push(int p, int l, int r) {
    if (!lz[p]) return;
    int mid = (l + r) >> 1;
    apply_(p << 1, mid - l + 1, lz[p]);
    apply_(p << 1 | 1, r - mid, lz[p]);
    lz[p] = 0;
}
static void build(int p, int l, int r) {
    lz[p] = 0;
    if (l == r) { sum[p] = w[rnk[l]] % MOD; return; }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); pull(p);
}
static void update(int p, int l, int r, int L, int R, long long v) {
    if (L <= l && r <= R) { apply_(p, r - l + 1, v); return; }
    push(p, l, r);
    int mid = (l + r) >> 1;
    if (L <= mid) update(p << 1, l, mid, L, R, v);
    if (R > mid) update(p << 1 | 1, mid + 1, r, L, R, v);
    pull(p);
}
static long long query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum[p];
    push(p, l, r);
    int mid = (l + r) >> 1;
    long long s = 0;
    if (L <= mid) s += query(p << 1, l, mid, L, R);
    if (R > mid) s += query(p << 1 | 1, mid + 1, r, L, R);
    return s % MOD;
}

/* ---------- 两趟遍历（都不递归） ---------- */
static void pass1() {
    int head = 0, tail = 0;
    bfsOrder[tail++] = root; fa[root] = 0; dep[root] = 1;
    while (head < tail) {
        int u = bfsOrder[head++];
        for (int v : g[u]) if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; bfsOrder[tail++] = v; }
    }
    for (int i = 1; i <= n; i++) { siz[i] = 1; son[i] = 0; }
    for (int i = n - 1; i >= 0; i--) {                  // 倒着扫 BFS 序 = 从叶子往根
        int u = bfsOrder[i], p = fa[u];
        if (!p) continue;
        siz[p] += siz[u];
        if (!son[p] || siz[u] > siz[son[p]]) son[p] = u;   // ★ 重儿子 = 子树最大的儿子
    }
}
static void pass2() {
    static int st[100005];
    int sp = 0;
    cnt = 0;
    top_[root] = root;
    st[sp++] = root;
    while (sp) {
        int u = st[--sp];
        dfn[u] = ++cnt; rnk[cnt] = u;
        /* ⚠ 栈是后进先出：轻儿子先压、重儿子后压 ⇒ 重儿子先被弹出
           ⇒ 一条重链上的 dfn 连成一段。这就是「重儿子优先」的全部含义。 */
        for (int v : g[u]) if (v != fa[u] && v != son[u]) { top_[v] = v; st[sp++] = v; }
        if (son[u]) { top_[son[u]] = top_[u]; st[sp++] = son[u]; }
    }
}

/* ---------- 路径 = O(log n) 段区间 ---------- */
static void pathAdd(int x, int y, long long z) {
    while (top_[x] != top_[y]) {
        if (dep[top_[x]] < dep[top_[y]]) swap(x, y);     // ★ 比的是链顶的深度，不是点的深度
        update(1, 1, n, dfn[top_[x]], dfn[x], z);
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    update(1, 1, n, dfn[x], dfn[y], z);                  // 最后一段：同一条链上的 x..y
}
static long long pathSum(int x, int y) {
    long long s = 0;
    while (top_[x] != top_[y]) {
        if (dep[top_[x]] < dep[top_[y]]) swap(x, y);
        s = (s + query(1, 1, n, dfn[top_[x]], dfn[x])) % MOD;
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return (s + query(1, 1, n, dfn[x], dfn[y])) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m >> root >> MOD)) return 0;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); }
    pass1(); pass2();
    build(1, 1, n);

    for (int i = 0; i < m; i++) {
        int op; cin >> op;
        if (op == 1) { int x, y; long long z; cin >> x >> y >> z; pathAdd(x, y, z % MOD); }
        else if (op == 2) { int x, y; cin >> x >> y; cout << pathSum(x, y) << '\n'; }
        else if (op == 3) { int x; long long z; cin >> x >> z; update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, z % MOD); }
        else { int x; cin >> x; cout << query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1) << '\n'; }
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★ 这份代码里，属于「这道题」而不属于「这一章」的只有五行

   cin >> n >> m >> root >> MOD;                  <- ① 根从这儿来，不是常数 1
   sum[p] = w[rnk[l]] % MOD;                      <- ② rnk：换过编号之后的翻译
   sum[p] = (sum[p] + v % MOD * len) % MOD;       <- ③④ 取模 ＋ long long
   pathAdd(x, y, z % MOD);                        <- ③ 读进来的 z 也先约一下
   update(..., dfn[x], dfn[x] + siz[x] - 1, ...); <- 子树 = 一段连续区间（任何 DFS 序都白送）

⇒ 剩下的一百行是第 53 章的内容。 ★★ 这正是这道题被叫做「模板题」的意思：难的那一半是通用的，而会让你 WA 的那几行是这道题自己的。

4★ 四个错法 × 六个档位 —— 一张表里三种性质完全不同的 0

p3384Root1.cpp✗ 错法①：忽略题面那个 R，从 1 号点开始剖分

p3384Build.cpp✗ 错法②：建树时用 w[l] 而不是 w[rnk[l]]

p3384LateMod.cpp✗ 错法③：线段树里一次模都不取，只在输出那一行取一次

p3384Int.cpp✗ 错法④：算法一个字没错，全程用 int

p3384Zero.cpp★ 试金石：什么都不算，一律输出 0

p3384Gen.cpp★ 生成器：六个档位

p3384Count.cpp★ 数触发条件：子树变没变 / 初值站没站错位 / 中间量有多大

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

// P3384 的「触发条件计数器」：`./p3384Count` 读一组数据，打一行 CSV
//
//   rootdiff  = 1 ⟺ 存在一次 op 3 / op 4，它的子树在「根 R」和「根 1」下**不是同一批点**
//                  （①Root1 的触发条件）
//   builddiff = 1 ⟺ 存在一个位置 l 使 `w[l] != w[rnk[l]]`（②Build 的触发条件）
//   maxmid    = 正解跑一遍，所有中间量绝对值的最大值（④Int 的触发条件：≥ 2³¹ 才可能烂）
//   rawmax    = 「一次模都不取」那一版跑一遍，最大的那个原始和（③LateMod：≥ 2⁶³ 才可能烂）
//
// ★ 后两个用 __int128 算，所以它自己不会溢出 —— 量溢出的尺子不能自己也溢出。
#include <bits/stdc++.h>
using namespace std;

static int n, m, root;
static long long MOD;
static vector<int> g[100005];
static long long w[100005];
static int fa[100005], dep[100005], siz[100005], son[100005];
static int top_[100005], dfn[100005], rnk[100005], bfsOrder[100005], cnt;
static long long sum_[400005], lz_[400005], maxmid;
static __int128 raw_[400005], rawlz_[400005], rawmax;

static void note(long long v) { maxmid = max(maxmid, v < 0 ? -v : v); }
static void noteRaw(__int128 v) { if (v < 0) v = -v; if (v > rawmax) rawmax = v; }

/* ---------- ① 取模那棵（跟正解逐字一致，只多了 note） ---------- */
static void pull(int p) { note(sum_[p << 1] + sum_[p << 1 | 1]); sum_[p] = (sum_[p << 1] + sum_[p << 1 | 1]) % MOD; }
static void apply_(int p, int len, long long v) {
    note(v % MOD * len);
    note(sum_[p] + v % MOD * len);
    sum_[p] = (sum_[p] + v % MOD * len) % MOD;
    lz_[p] = (lz_[p] + v) % MOD;
}
static void push(int p, int l, int r) {
    if (!lz_[p]) return;
    int mid = (l + r) >> 1;
    apply_(p << 1, mid - l + 1, lz_[p]); apply_(p << 1 | 1, r - mid, lz_[p]);
    lz_[p] = 0;
}
static void build(int p, int l, int r) {
    lz_[p] = 0;
    if (l == r) { sum_[p] = w[rnk[l]] % MOD; note(sum_[p]); return; }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); pull(p);
}
static void update(int p, int l, int r, int L, int R, long long v) {
    if (L <= l && r <= R) { apply_(p, r - l + 1, v); return; }
    push(p, l, r);
    int mid = (l + r) >> 1;
    if (L <= mid) update(p << 1, l, mid, L, R, v);
    if (R > mid) update(p << 1 | 1, mid + 1, r, L, R, v);
    pull(p);
}
static long long query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum_[p];
    push(p, l, r);
    int mid = (l + r) >> 1;
    long long s = 0;
    if (L <= mid) s += query(p << 1, l, mid, L, R);
    if (R > mid) s += query(p << 1 | 1, mid + 1, r, L, R);
    note(s);
    return s % MOD;
}

/* ---------- ② 一次模都不取那棵（用 __int128，量尺子自己不许溢出） ---------- */
static void rPull(int p) { raw_[p] = raw_[p << 1] + raw_[p << 1 | 1]; noteRaw(raw_[p]); }
static void rApply(int p, int len, __int128 v) { raw_[p] += v * len; rawlz_[p] += v; noteRaw(raw_[p]); }
static void rPush(int p, int l, int r) {
    if (!rawlz_[p]) return;
    int mid = (l + r) >> 1;
    rApply(p << 1, mid - l + 1, rawlz_[p]); rApply(p << 1 | 1, r - mid, rawlz_[p]);
    rawlz_[p] = 0;
}
static void rBuild(int p, int l, int r) {
    rawlz_[p] = 0;
    if (l == r) { raw_[p] = w[rnk[l]]; noteRaw(raw_[p]); return; }
    int mid = (l + r) >> 1;
    rBuild(p << 1, l, mid); rBuild(p << 1 | 1, mid + 1, r); rPull(p);
}
static void rUpdate(int p, int l, int r, int L, int R, __int128 v) {
    if (L <= l && r <= R) { rApply(p, r - l + 1, v); return; }
    rPush(p, l, r);
    int mid = (l + r) >> 1;
    if (L <= mid) rUpdate(p << 1, l, mid, L, R, v);
    if (R > mid) rUpdate(p << 1 | 1, mid + 1, r, L, R, v);
    rPull(p);
}
static __int128 rQuery(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return raw_[p];
    rPush(p, l, r);
    int mid = (l + r) >> 1;
    __int128 s = 0;
    if (L <= mid) s += rQuery(p << 1, l, mid, L, R);
    if (R > mid) s += rQuery(p << 1 | 1, mid + 1, r, L, R);
    noteRaw(s);
    return s;
}

static void pass1(int rt) {
    int head = 0, tail = 0;
    bfsOrder[tail++] = rt; fa[rt] = 0; dep[rt] = 1;
    while (head < tail) {
        int u = bfsOrder[head++];
        for (int v : g[u]) if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; bfsOrder[tail++] = v; }
    }
    for (int i = 1; i <= n; i++) { siz[i] = 1; son[i] = 0; }
    for (int i = n - 1; i >= 0; i--) {
        int u = bfsOrder[i], p = fa[u];
        if (!p) continue;
        siz[p] += siz[u];
        if (!son[p] || siz[u] > siz[son[p]]) son[p] = u;
    }
}
static void pass2(int rt) {
    static int st[100005];
    int sp = 0; cnt = 0;
    top_[rt] = rt; st[sp++] = rt;
    while (sp) {
        int u = st[--sp];
        dfn[u] = ++cnt; rnk[cnt] = u;
        for (int v : g[u]) if (v != fa[u] && v != son[u]) { top_[v] = v; st[sp++] = v; }
        if (son[u]) { top_[son[u]] = top_[u]; st[sp++] = son[u]; }
    }
}
static void pathAdd(int x, int y, long long z) {
    while (top_[x] != top_[y]) {
        if (dep[top_[x]] < dep[top_[y]]) swap(x, y);
        update(1, 1, n, dfn[top_[x]], dfn[x], z);
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    update(1, 1, n, dfn[x], dfn[y], z);
}
static void rPathAdd(int x, int y, __int128 z) {
    while (top_[x] != top_[y]) {
        if (dep[top_[x]] < dep[top_[y]]) swap(x, y);
        rUpdate(1, 1, n, dfn[top_[x]], dfn[x], z);
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    rUpdate(1, 1, n, dfn[x], dfn[y], z);
}
static void rPathSum(int x, int y) {
    __int128 s = 0;
    while (top_[x] != top_[y]) {
        if (dep[top_[x]] < dep[top_[y]]) swap(x, y);
        s += rQuery(1, 1, n, dfn[top_[x]], dfn[x]);
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    s += rQuery(1, 1, n, dfn[x], dfn[y]);
    noteRaw(s);
}
static long long pathSum(int x, int y) {
    long long s = 0;
    while (top_[x] != top_[y]) {
        if (dep[top_[x]] < dep[top_[y]]) swap(x, y);
        s = (s + query(1, 1, n, dfn[top_[x]], dfn[x])) % MOD;
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return (s + query(1, 1, n, dfn[x], dfn[y])) % MOD;
}

/** 以 rt 为根时 x 的子树（点集，按编号排序）*/
static vector<int> subtreeOf(int rt, int x) {
    vector<int> par(n + 1, 0), order;
    order.push_back(rt); par[rt] = -1;
    for (size_t i = 0; i < order.size(); i++) {
        int u = order[i];
        for (int v : g[u]) if (v != par[u]) { par[v] = u; order.push_back(v); }
    }
    vector<int> res, st{x};
    vector<char> vis(n + 1, 0); vis[x] = 1;
    while (!st.empty()) {
        int u = st.back(); st.pop_back(); res.push_back(u);
        for (int v : g[u]) if (v != par[u] && !vis[v]) { vis[v] = 1; st.push_back(v); }
    }
    sort(res.begin(), res.end());
    return res;
}

int main() {
    if (scanf("%d %d %d %lld", &n, &m, &root, &MOD) != 4) return 0;
    for (int i = 1; i <= n; i++) if (scanf("%lld", &w[i]) != 1) return 0;
    for (int i = 1; i < n; i++) { int a, b; if (scanf("%d %d", &a, &b) != 2) return 0; g[a].push_back(b); g[b].push_back(a); }
    struct Op { int op, x, y; long long z; };
    vector<Op> ops;
    for (int i = 0; i < m; i++) {
        Op o{}; if (scanf("%d", &o.op) != 1) return 0;
        if (o.op == 1) { if (scanf("%d %d %lld", &o.x, &o.y, &o.z) != 3) return 0; }
        else if (o.op == 2) { if (scanf("%d %d", &o.x, &o.y) != 2) return 0; }
        else if (o.op == 3) { if (scanf("%d %lld", &o.x, &o.z) != 2) return 0; }
        else { if (scanf("%d", &o.x) != 1) return 0; }
        ops.push_back(o);
    }

    int rootdiff = 0;
    for (const Op& o : ops)
        if (o.op >= 3 && subtreeOf(root, o.x) != subtreeOf(1, o.x)) { rootdiff = 1; break; }

    pass1(root); pass2(root);
    int builddiff = 0;
    for (int l = 1; l <= n; l++) if (w[l] != w[rnk[l]]) { builddiff = 1; break; }

    build(1, 1, n);
    for (const Op& o : ops) {
        if (o.op == 1) pathAdd(o.x, o.y, o.z % MOD);
        else if (o.op == 2) pathSum(o.x, o.y);
        else if (o.op == 3) update(1, 1, n, dfn[o.x], dfn[o.x] + siz[o.x] - 1, o.z % MOD);
        else query(1, 1, n, dfn[o.x], dfn[o.x] + siz[o.x] - 1);
    }
    rBuild(1, 1, n);
    for (const Op& o : ops) {
        if (o.op == 1) rPathAdd(o.x, o.y, o.z);
        else if (o.op == 2) rPathSum(o.x, o.y);
        else if (o.op == 3) rUpdate(1, 1, n, dfn[o.x], dfn[o.x] + siz[o.x] - 1, o.z);
        else rQuery(1, 1, n, dfn[o.x], dfn[o.x] + siz[o.x] - 1);
    }
    /* __int128 打印：拆成两段 */
    char buf[64]; int bl = 0; __int128 t = rawmax;
    if (t == 0) buf[bl++] = '0';
    while (t > 0) { buf[bl++] = char('0' + (int)(t % 10)); t /= 10; }
    printf("rootdiff,%d\nbuilddiff,%d\nmaxmid,%lld\nrawmax,", rootdiff, builddiff, maxmid);
    for (int i = bl - 1; i >= 0; i--) putchar(buf[i]);
    putchar('\n');
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

★★★ 300 轮 × 六档（本机实测）

档位	①Root1	②Build	④Int	试金石
0 顺手写法	122	232	0	271
1 根固定为 1	★ 0	202	0	271
2 所有点权都相同	118	★ 0	0	262
3 `P`、`z` 顶到 2³⁰	123	233	23	271
4 最终档	232	300	169	300
5 初值和 `z` 全为 0	⚠ 0	0	0	⚠ 0

★★★ 一张表里，三种性质完全不同的 0：

那个 0 是哪一种	谁	怎么救
结构性的 0（能证）	①档 1、②档 2	那正是它们的自检
档位到不了那条线	③LateMod（六档全零）、④档 0~2	换档位，见第 ⑤ 步
这一档在验零	档 5 整行	换生成器

★ 那两个「结构性的 0」都是一行能证的： ① 根本来就是 1 ⇒ 忽略 R 和不忽略是同一件事； ② 所有点权都一样 ⇒ 放在哪个位置上都一样，rnk 那一步翻译不翻译毫无区别。

⚠ 而档 5 是整整一档在验零：初值和所有 z 都是 0 ⇒ 正确答案恒等于 0 ⇒ 四个错法连同试金石全部满分。 ⇒ 「一致有两种：都算对了，和都没算」。

★★ 三个错法的「触发 ≡ 抓获」，三种结局

	第一层（触发条件）	抓获
①Root1	存在一次 op3/op4，两种根下的子树不是同一批点：161 / 0 / 149 / 161 / 238 / 153	122 / 0 / 118 / 123 / 232 / 0	⚠ 差 1.3 倍
②Build	存在位置 `l` 使 `w[l] != w[rnk[l]]`：271 / 237 / 0 / 271 / 300 / 0	232 / 202 / 0 / 233 / 300 / 0	⚠ 差 1.2 倍
④Int	中间量最大值 ≥ 2³¹：0 / 0 / 0 / 124 / 258 / 0	0 / 0 / 0 / 23 / 169 / 0	⚠ 差 5.4 倍

⇒ ★★ 三条都是「触发是必要条件，不是充分条件」：子树变了、但那次 op3 改的值后面没人问／初值站错了位、但那个位置没被读到／中间量越了界、但越界的那一格没被读到。 ⇒ 第 52 章 P2680 那条的又一次，而这一页一口气给了三个。

★ 反过来说，三条的第一层全都是精确的：结构性的 0 那四格（①档 1 的 0、②档 2 和档 5 的 0、④档 0~2 的 0），触发和抓获逐格相同。

★ 官方样例挡住了两个，而放过的那两个原因是同一个

	样例上的输出
★ 正解	`2` `21`
①Root1	`0` `17`	✓ 挡住了 —— 样例的 `R` 正好是 2，不是 1
②Build	`2` `18`	✓ 挡住了
③LateMod	`2` `21`	✗ 放过
④Int	`2` `21`	✗ 放过

⇒ 放过的两个原因是同一个：样例的 P 只有 24，五个点、五个操作 —— 两条线（2³¹ 和 2⁶³）都差着七八个数量级。 ★ 而挡住 ①Root1 那一格值得单说：出题人把根写成了 2 —— 如果他顺手写 1，这道模板题最容易犯的那个错就一组样例都测不出来。

5⚠ ③LateMod 是「对拍永远抓不到」的那一类 —— 而这次差 1.45 亿倍

p3384Line.cpp★ 探针：造一条指定长度的链，把「不取模」那一版逼到 long long 的边上

★★ 先算，再拿真程序在两侧各跑一遍

「一次模都不取、只在输出取一次」——它在小数据上一个字都不错（取模是同态的）。它唯一的问题是 long long 装不装得下，而那条线算得出来：

   顶格：每次 1 x y z 给整条路径加 z ⇒ 单点攒到 m·z，一条路径 n 个点 ⇒ n·m·z
   题面只说「所有输入的数均在 int 范围内」⇒ 取 z = 2³⁰
   2⁶³ / (10⁵ × 2³⁰) = 2³³ / 10⁵ = 85899.34592
   ⇒ 链长 85899 塞得下，85900 塞不下   （而 n 可以到 10⁵）

⚠⚠ 而这条线不能拿同一个公式再算一遍来自检（第 48 章 P3435 那一课）—— 拿真程序在两侧各跑一遍：

链长 `L`	★ 正解	✗ ③LateMod
85898	1069040869	1069040869
85899	1072540869	★ 1072540869
85900	2299080	⚠ −1071462309
85901	5799080	−1067962309

⇒ ★★★ 而对拍那六档里，最大的那个原始和只有 6.37 × 10¹⁰ —— 离 2⁶³ = 9.22 × 10¹⁸ 差 1.45 亿倍。 ⇒ 这是第 48 章 P3435「档位到不了那条线」那一类 0 的又一次，而它比第 52 章 P3178 那次的 107 倍狠了六个数量级： 加多少轮都没有用，只能换档位。

6★ 哪一版就已经能过了

★★ 结论

版本	能过吗	数字（顶格最坏形状 `chain`）
✗ 照题面直做（暴力）	✗	22.39 秒 / 时限 1 秒（⚠ 但顶格随机只要 0.04 秒）
✗ 忽略 `R`	✗	op 3 / op 4 全废，op 1 / op 2 全对
✗ 建树忘了 `rnk`	✗	初值整体站错位
✗ 只在输出取模	✗	链长 ≥ 85900 就烂（而 `n ≤ 10⁵`）
✗ 全程 `int`	✗	`v % MOD * len`，`P` 大一点就烂
★ 正解	✓	0.13 秒（最慢那一档）、峰值 17.4 MiB / 128 MiB

⇒ 这道题的四件功课，一件都不在树链剖分上： ① 根是 R；② 建树要按 rnk 翻译；③ 每一步都取模；④ long long。

★ 一句话带走

模板题的意思不是「照抄模板就完了」，是「难的那一半是通用的，而会让你 WA 的那几行是这道题自己的」。

⇒ 树链剖分这一百行，你抄一次就能用一辈子；而「根在哪儿、初值怎么摆、模数是几、装不装得下」这四句，每道题都得重新读一遍题面。 ★ 这一页四个错法，没有一个跟「路径怎么砍成区间」有关系。