1. 树链剖分基础回顾树链剖分Heavy-Light Decomposition是处理树上路径问题的利器它通过将树分解为若干条链使得我们能够高效地处理路径查询和修改。在进入练习题之前我们先快速回顾几个核心概念重儿子对于每个非叶子节点其子树大小最大的子节点称为重儿子轻儿子非重儿子的其他子节点重链由重儿子连接形成的链轻边连接两个轻儿子的边这种分解方式有一个重要性质从任意节点到根节点的路径上最多只有O(log n)条重链和轻边。正是这个性质保证了树链剖分算法的高效性。2. 题目分析与建模这道练习题要求我们实现一个支持两种操作的树结构对某条路径上的所有节点权值增加一个值查询某条路径上的节点权值和这类路径操作问题正是树链剖分的典型应用场景。我们需要先将树分解为链然后使用线段树或树状数组等数据结构来维护每条链上的信息。2.1 输入数据预处理首先我们需要处理输入数据并构建树结构。假设输入格式如下第一行n节点数接下来n-1行每行两个数u,v表示一条边然后是m个操作1 u v w将u到v路径上的节点权值加w2 u v查询u到v路径上的节点权值和const int MAXN 1e5 5; vectorint G[MAXN]; int n, m; void input() { cin n; for (int i 1; i n; i) { int u, v; cin u v; G[u].push_back(v); G[v].push_back(u); } }3. 树链剖分实现3.1 第一次DFS确定重儿子我们需要两次DFS来完成树链剖分的预处理。第一次DFS计算每个节点的子树大小并确定重儿子。int fa[MAXN], dep[MAXN], siz[MAXN], son[MAXN]; void dfs1(int u, int f) { fa[u] f; dep[u] dep[f] 1; siz[u] 1; for (int v : G[u]) { if (v f) continue; dfs1(v, u); siz[u] siz[v]; if (siz[v] siz[son[u]]) son[u] v; } }3.2 第二次DFS构建重链第二次DFS为节点分配链上的位置dfs序并记录链顶。int top[MAXN], dfn[MAXN], cnt; void dfs2(int u, int tp) { top[u] tp; dfn[u] cnt; if (son[u]) dfs2(son[u], tp); // 优先处理重儿子 for (int v : G[u]) { if (v fa[u] || v son[u]) continue; dfs2(v, v); // 轻儿子作为新链的起点 } }4. 线段树实现为了高效处理路径上的区间操作和查询我们需要实现一个支持区间加和区间求和的线段树。struct SegmentTree { struct Node { int l, r; int sum, add; } tr[MAXN 2]; void pushup(int u) { tr[u].sum tr[u1].sum tr[u1|1].sum; } void pushdown(int u) { if (tr[u].add) { int mid (tr[u].l tr[u].r) 1; tr[u1].sum tr[u].add * (mid - tr[u].l 1); tr[u1|1].sum tr[u].add * (tr[u].r - mid); tr[u1].add tr[u].add; tr[u1|1].add tr[u].add; tr[u].add 0; } } void build(int u, int l, int r) { tr[u] {l, r, 0, 0}; if (l r) return; int mid (l r) 1; build(u1, l, mid); build(u1|1, mid1, r); } void update(int u, int l, int r, int val) { if (tr[u].l l tr[u].r r) { tr[u].sum val * (tr[u].r - tr[u].l 1); tr[u].add val; return; } pushdown(u); int mid (tr[u].l tr[u].r) 1; if (l mid) update(u1, l, r, val); if (r mid) update(u1|1, l, r, val); pushup(u); } int query(int u, int l, int r) { if (tr[u].l l tr[u].r r) return tr[u].sum; pushdown(u); int mid (tr[u].l tr[u].r) 1; int res 0; if (l mid) res query(u1, l, r); if (r mid) res query(u1|1, l, r); return res; } } st;5. 路径操作实现有了树链剖分和线段树的基础现在我们可以实现题目要求的两种路径操作。5.1 路径加操作void path_add(int u, int v, int w) { while (top[u] ! top[v]) { if (dep[top[u]] dep[top[v]]) swap(u, v); st.update(1, dfn[top[u]], dfn[u], w); u fa[top[u]]; } if (dep[u] dep[v]) swap(u, v); st.update(1, dfn[u], dfn[v], w); }5.2 路径查询操作int path_query(int u, int v) { int res 0; while (top[u] ! top[v]) { if (dep[top[u]] dep[top[v]]) swap(u, v); res st.query(1, dfn[top[u]], dfn[u]); u fa[top[u]]; } if (dep[u] dep[v]) swap(u, v); res st.query(1, dfn[u], dfn[v]); return res; }6. 完整代码实现将上述各部分组合起来我们得到完整的解决方案#include iostream #include vector using namespace std; const int MAXN 1e5 5; vectorint G[MAXN]; int n, m; // 树链剖分部分 int fa[MAXN], dep[MAXN], siz[MAXN], son[MAXN]; int top[MAXN], dfn[MAXN], cnt; void dfs1(int u, int f) { fa[u] f; dep[u] dep[f] 1; siz[u] 1; for (int v : G[u]) { if (v f) continue; dfs1(v, u); siz[u] siz[v]; if (siz[v] siz[son[u]]) son[u] v; } } void dfs2(int u, int tp) { top[u] tp; dfn[u] cnt; if (son[u]) dfs2(son[u], tp); for (int v : G[u]) { if (v fa[u] || v son[u]) continue; dfs2(v, v); } } // 线段树部分 struct SegmentTree { struct Node { int l, r; int sum, add; } tr[MAXN 2]; void pushup(int u) { tr[u].sum tr[u1].sum tr[u1|1].sum; } void pushdown(int u) { if (tr[u].add) { int mid (tr[u].l tr[u].r) 1; tr[u1].sum tr[u].add * (mid - tr[u].l 1); tr[u1|1].sum tr[u].add * (tr[u].r - mid); tr[u1].add tr[u].add; tr[u1|1].add tr[u].add; tr[u].add 0; } } void build(int u, int l, int r) { tr[u] {l, r, 0, 0}; if (l r) return; int mid (l r) 1; build(u1, l, mid); build(u1|1, mid1, r); } void update(int u, int l, int r, int val) { if (tr[u].l l tr[u].r r) { tr[u].sum val * (tr[u].r - tr[u].l 1); tr[u].add val; return; } pushdown(u); int mid (tr[u].l tr[u].r) 1; if (l mid) update(u1, l, r, val); if (r mid) update(u1|1, l, r, val); pushup(u); } int query(int u, int l, int r) { if (tr[u].l l tr[u].r r) return tr[u].sum; pushdown(u); int mid (tr[u].l tr[u].r) 1; int res 0; if (l mid) res query(u1, l, r); if (r mid) res query(u1|1, l, r); return res; } } st; // 路径操作 void path_add(int u, int v, int w) { while (top[u] ! top[v]) { if (dep[top[u]] dep[top[v]]) swap(u, v); st.update(1, dfn[top[u]], dfn[u], w); u fa[top[u]]; } if (dep[u] dep[v]) swap(u, v); st.update(1, dfn[u], dfn[v], w); } int path_query(int u, int v) { int res 0; while (top[u] ! top[v]) { if (dep[top[u]] dep[top[v]]) swap(u, v); res st.query(1, dfn[top[u]], dfn[u]); u fa[top[u]]; } if (dep[u] dep[v]) swap(u, v); res st.query(1, dfn[u], dfn[v]); return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; for (int i 1; i n; i) { int u, v; cin u v; G[u].push_back(v); G[v].push_back(u); } dfs1(1, 0); dfs2(1, 1); st.build(1, 1, n); cin m; while (m--) { int op, u, v, w; cin op; if (op 1) { cin u v w; path_add(u, v, w); } else { cin u v; cout path_query(u, v) \n; } } return 0; }7. 复杂度分析与优化7.1 时间复杂度分析树链剖分预处理两次DFSO(n)每条重链处理O(log n)条链线段树操作每条链O(log n)总复杂度每次路径操作O(log² n)7.2 空间复杂度树结构O(n)线段树O(n)总空间O(n)7.3 优化技巧使用树状数组代替线段树如果只需要单点查询树状数组常数更小内存池优化对于大规模数据可以使用内存池来减少动态内存分配开销输入输出优化使用快速IO可以显著提升性能8. 常见问题与调试技巧8.1 常见错误DFS栈溢出对于深度较大的树递归DFS可能导致栈溢出可以改为非递归实现线段树边界错误特别注意线段树的区间边界处理重链跳转错误在路径操作中必须始终向链顶深度较大的方向跳转8.2 调试建议打印树链剖分结果验证每个节点的dfn、top等属性是否正确小数据测试构造小规模的测试用例手工验证结果对拍测试与暴力解法对比结果确保正确性调试时可以添加以下打印函数void debug_print() { cout 节点信息 endl; for (int i 1; i n; i) { cout 节点 i : dfn dfn[i] , top top[i] , son son[i] , siz siz[i] endl; } }9. 扩展应用树链剖分的应用不仅限于路径求和还可以解决许多其他树上路径问题路径最大值/最小值查询修改线段树维护的信息即可子树操作利用dfn的连续性子树操作对应区间操作边权转点权将边权赋给深度较大的端点可以处理边权问题动态树问题结合LCT可以处理动态树问题10. 实战练习建议要熟练掌握树链剖分建议按以下顺序练习基础路径求和问题如本题路径最大值/最小值问题边权转点权问题结合其他数据结构的复合问题一些推荐练习题模板题路径加、路径求和进阶题路径染色、统计颜色段挑战题动态树问题需要结合LCT在实际编码时建议先写好框架再填充细节特别注意边界条件的处理。树链剖分的代码量较大但结构相对固定熟练掌握后可以快速解决许多复杂的树上路径问题。