From 00a48068b9ec28e03a45c8fa826b91f567e11e51 Mon Sep 17 00:00:00 2001 From: Ir1dXD Date: Thu, 6 Sep 2018 10:51:16 +0800 Subject: [PATCH] Update heavy-light-decomposition.md --- docs/graph/heavy-light-decomposition.md | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/docs/graph/heavy-light-decomposition.md b/docs/graph/heavy-light-decomposition.md index a76ce956..d5a2e703 100644 --- a/docs/graph/heavy-light-decomposition.md +++ b/docs/graph/heavy-light-decomposition.md @@ -6,9 +6,9 @@ By [hsfzLZH1](https://github.com/hsfzLZH1) 一棵静态（形状固定的）树，要求进行几种操作： -1.修改 **单个节点/树上两点之间的最短路径/一个节点的子树上** 的所有点的值。 +1.修改 **单个节点 / 树上两点之间的路径 / 一个节点的子树上** 的所有点的值。 -2.查询 **单个节点/树上两点之间的最短路径/一个节点的子树上** 节点的值的 **和/极值/其他（具有较强的合并性）** 。 +2.查询 **单个节点 / 树上两点之间的路径 / 一个节点的子树上** 节点的值的 **和 / 极值 / 其他（具有较强的合并性）** 。 如果树的形态是一条链，那么我们只需要维护一个线段树，修改或查询线段树的值。 @@ -24,9 +24,9 @@ By [hsfzLZH1](https://github.com/hsfzLZH1) 1. 修改单个节点的值； -2. 查询 $u$ 到 $v$ 的最短路径上的最大值； +2. 查询 $u$ 到 $v$ 的路径上的最大值； -3. 查询 $u$ 到 $v$ 的最短路径上的权值和。 +3. 查询 $u$ 到 $v$ 的路径上的权值和。 题目保证 $1\le n\le 30000,0\le q\le 200000$ @@ -93,7 +93,7 @@ void dfs2(int o,int t) 修改一个节点的子树也很容易实现。 -问题是如何修改/查询两个节点之间的最短路径。 +问题是如何修改/查询两个节点之间的路径。 考虑我们是如何用 **倍增法求解LCA** 的。首先我们 **将两个节点提到同一高度，然后将两个节点一起向上跳** 。对于树链剖分也可以使用这样的思想。 -- 2.11.0