【模板】重链剖分 / 树链剖分

题意

支持树上路径加、路径和、子树加和子树和，结果对 P 取模。

思路

重链剖分把任意路径拆成 O(log n) 个连续 DFS 序区间；子树天然是 [dfn[x], dfn[x]+size[x)-1]。线段树保存区间和并懒加，逐段处理路径即可。

Python 知识

用栈保存 (node, chain_top)，沿重儿子迭代，避免递归分解。
list(map(int, input().split())) 统一读取四种操作长度。
模运算集中放在 apply 和合并处，保持节点值有界。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
140import sys


sys.setrecursionlimit(1_000_000)
input = sys.stdin.buffer.readline
n, operations, root, modulus = map(int, input().split())
values = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

parent = [0] * (n + 1)
depth = [0] * (n + 1)
order = [root]
for node in order:
    for neighbor in graph[node]:
        if neighbor != parent[node]:
            parent[neighbor] = node
            depth[neighbor] = depth[node] + 1
            order.append(neighbor)
subtree = [1] * (n + 1)
heavy = [0] * (n + 1)
for node in reversed(order[1:]):
    subtree[parent[node]] += subtree[node]
    if subtree[node] > subtree[heavy[parent[node]]]:
        heavy[parent[node]] = node

top = [0] * (n + 1)
dfn = [0] * (n + 1)
timer = 0
chains = [(root, root)]
while chains:
    node, chain_top = chains.pop()
    while node:
        top[node] = chain_top
        timer += 1
        dfn[node] = timer
        for neighbor in graph[node]:
            if neighbor != parent[node] and neighbor != heavy[node]:
                chains.append((neighbor, neighbor))
        node = heavy[node]

tree = [0] * (4 * n)
lazy = [0] * (4 * n)


base = [0] * (n + 1)
for node in range(1, n + 1):
    base[dfn[node]] = values[node] % modulus


def build_fast(node, left, right):
    if left == right:
        tree[node] = base[left]
        return
    middle = (left + right) // 2
    build_fast(node * 2, left, middle)
    build_fast(node * 2 + 1, middle + 1, right)
    tree[node] = (tree[node * 2] + tree[node * 2 + 1]) % modulus


def apply(node, length, value):
    tree[node] = (tree[node] + length * value) % modulus
    lazy[node] = (lazy[node] + value) % modulus


def push(node, left, right):
    if lazy[node] and left != right:
        middle = (left + right) // 2
        apply(node * 2, middle - left + 1, lazy[node])
        apply(node * 2 + 1, right - middle, lazy[node])
        lazy[node] = 0


def update(node, left, right, query_left, query_right, value):
    if query_left <= left and right <= query_right:
        apply(node, right - left + 1, value)
        return
    push(node, left, right)
    middle = (left + right) // 2
    if query_left <= middle:
        update(node * 2, left, middle, query_left, query_right, value)
    if middle < query_right:
        update(node * 2 + 1, middle + 1, right, query_left, query_right, value)
    tree[node] = (tree[node * 2] + tree[node * 2 + 1]) % modulus


def query(node, left, right, query_left, query_right):
    if query_left <= left and right <= query_right:
        return tree[node]
    push(node, left, right)
    middle = (left + right) // 2
    answer = 0
    if query_left <= middle:
        answer += query(node * 2, left, middle, query_left, query_right)
    if middle < query_right:
        answer += query(node * 2 + 1, middle + 1, right, query_left, query_right)
    return answer % modulus


build_fast(1, 1, n)


def path_update(x, y, value):
    while top[x] != top[y]:
        if depth[top[x]] < depth[top[y]]:
            x, y = y, x
        update(1, 1, n, dfn[top[x]], dfn[x], value)
        x = parent[top[x]]
    if depth[x] > depth[y]:
        x, y = y, x
    update(1, 1, n, dfn[x], dfn[y], value)


def path_query(x, y):
    answer = 0
    while top[x] != top[y]:
        if depth[top[x]] < depth[top[y]]:
            x, y = y, x
        answer += query(1, 1, n, dfn[top[x]], dfn[x])
        x = parent[top[x]]
    if depth[x] > depth[y]:
        x, y = y, x
    return (answer + query(1, 1, n, dfn[x], dfn[y])) % modulus


answers = []
for _ in range(operations):
    operation = list(map(int, input().split()))
    if operation[0] == 1:
        path_update(operation[1], operation[2], operation[3] % modulus)
    elif operation[0] == 2:
        answers.append(str(path_query(operation[1], operation[2])))
    elif operation[0] == 3:
        update(1, 1, n, dfn[operation[1]], dfn[operation[1]] + subtree[operation[1]] - 1, operation[2] % modulus)
    else:
        answers.append(str(query(1, 1, n, dfn[operation[1]], dfn[operation[1]] + subtree[operation[1]] - 1)))
print("\n".join(answers))

原有 C++ 版本仍保留：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
 * 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-07-17 01:04
 * update_at: 2026-07-17 01:04
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
}

复杂度

预处理 O(n)，每次操作 O(log^2 n)，空间 O(n)。

总结

HLD 的接口就是“路径拆段 + 区间数据结构”；先掌握拆段循环，再替换线段树统计量。

【模板】重链剖分 / 树链剖分

目录

题意

思路

Python 知识

代码

复杂度

总结