3

P3384

gitea-actions[bot] edited this page 2026-10-29 06:04:43 +00:00

Table of Contents

• P3384 【模板】重链剖分 / 树链剖分 题解

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

重链剖分模板。习惯用线段树（也可以双 BIT）。

其中：

• L13-48 为维护区间和的线段树。
• L49-59 为 dfs1，处理 $dep, cnt, fa, son$。
• L60-71 为 dfs2，处理 $dfn, top$。
• L72-80 为路径加，上跳即可。
• L81-90 为路径查询，与修改是类似的。
• L91-96 为子树修改与查询，由于子树的 dfn 序列是连续的，直接在线段树上修改即可。

接下来建议用树链剖分解决一些简单题。

code

题解

🏠 返回仓库

根目录

• AT_agc013_e
• AT_arc073_b
• CF739A
• CF1187E
• CF1380D
• CF1912E
• P1453
• P2016
• P2607
• P3199
• P3205
• P3384
• P3572
• P4211
• P4342
• P6650
• P7458
• P7707
• P13366
• P16055
• P16060
• P17437