From fe343b95a0143040ce15d9ce34ae15d66a4109e3 Mon Sep 17 00:00:00 2001 From: Yupeng Hou Date: Wed, 25 Sep 2019 11:58:11 +0800 Subject: [PATCH] Apply suggestions from code review Co-Authored-By: ouuan --- docs/graph/hld.md | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/docs/graph/hld.md b/docs/graph/hld.md index 5b28e2da..e01cad59 100644 --- a/docs/graph/hld.md +++ b/docs/graph/hld.md @@ -63,7 +63,7 @@ $$ \end{array} $$ -第二个 DFS 记录所在链的链顶(top,应初始化为结点本身)、重边优先遍历时的 DFS 序(dfn)、DFN 对应的节点编号(rank)。 +第二个 DFS 记录所在链的链顶(top,应初始化为结点本身)、重边优先遍历时的 DFS 序(dfn)、DFS 序对应的节点编号(rank)。 $$ \begin{array}{l} @@ -133,9 +133,9 @@ void dfs2(int o, int t) { 重链一定是链状结构;重边不会连成一棵树。 -在剖分时 **重边优先遍历** ,最后树的 DFS 序上,重链内的 DFN 是连续的。按 DFN 排序后的序列即为剖分后的链。 +在剖分时 **优先遍历重边** ,最后重链的 DFS 序就会是连续的。 -一颗子树内的 DFN 是连续的。 +一颗子树内的 DFS 序是连续的。 可以发现,当我们向下经过一条 **轻边** 时,所在子树的大小至少会除以二。 @@ -173,7 +173,7 @@ $$ 有时会要求,维护子树上的信息,譬如将以 x 为根的子树的所有结点的权值增加 v。 -在 DFS 搜索的时候,子树中的结点的 DFN 是连续的。 +在 DFS 搜索的时候,子树中的结点的 DFS 序是连续的。 每一个结点记录 bottom 表示所在子树连续区间末端的结点。 -- 2.11.0