From ffa1fd37ddb78e010c2285cb15a6b7e6c821a3be Mon Sep 17 00:00:00 2001 From: Ir1dXD Date: Sun, 30 Jun 2019 21:09:28 +0800 Subject: [PATCH] Update heavy-light-decomposition.md --- docs/graph/heavy-light-decomposition.md | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) diff --git a/docs/graph/heavy-light-decomposition.md b/docs/graph/heavy-light-decomposition.md index f0d126e1..26744ffb 100644 --- a/docs/graph/heavy-light-decomposition.md +++ b/docs/graph/heavy-light-decomposition.md @@ -68,13 +68,13 @@ TREE-DECOMPOSITION-DFS(u,top) 我们先给出一些定义： -1. $fa(x)$ 表示节点 $x$ 在树上的父亲。 -2. $dep(x)$ 表示节点 $x$ 在树上的深度。 -3. $siz(x)$ 表示节点 $x$ 的子树的节点个数。 -4. $son(x)$ 表示节点 $x$ 的 **重儿子** 。 -5. $top(x)$ 表示节点 $x$ 所在 **重链** 的顶部节点（深度最小）。 -6. $tid(x)$ 表示节点 $x$ 的 **时间戳** ，也是其在线段树中的编号。 -7. $rnk(x)$ 表示时间戳所对应的节点编号，有 $rnk(tid(x))=x$ 。 +- $fa(x)$ 表示节点 $x$ 在树上的父亲。 +- $dep(x)$ 表示节点 $x$ 在树上的深度。 +- $siz(x)$ 表示节点 $x$ 的子树的节点个数。 +- $son(x)$ 表示节点 $x$ 的 **重儿子** 。 +- $top(x)$ 表示节点 $x$ 所在 **重链** 的顶部节点（深度最小）。 +- $tid(x)$ 表示节点 $x$ 的 **时间戳** ，也是其在线段树中的编号。 +- $rnk(x)$ 表示时间戳所对应的节点编号，有 $rnk(tid(x))=x$ 。 我们进行两遍 DFS 预处理出这些值，其中第一次 DFS 求出 $fa(x),dep(x),siz(x),son(x)$ ，第二次 DFS 求出 $top(x),tid(x),rnk(x)$ 。 @@ -157,7 +157,7 @@ TREE-PATH-SUM(u,v) 不断向上跳链，当跳到同一条链上时，返回深度较小的结点即为 LCA。 -## 例题：[「ZJOI2008」树的统计](https://www.luogu.org/problemnew/show/P2590) +## 例题：[「ZJOI2008」树的统计](https://www.lydsy.com/JudgeOnline/problem.php?id=1036) ### 题目大意 -- 2.11.0