From 9ce7d4dca85a610453b891e2f82fe80954f2ad84 Mon Sep 17 00:00:00 2001 From: Penguint Date: Mon, 9 Nov 2020 05:47:44 +0800 Subject: [PATCH] fix: typo --- docs/graph/dsu-on-tree.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/docs/graph/dsu-on-tree.md b/docs/graph/dsu-on-tree.md index 43a54c09..6af39f99 100644 --- a/docs/graph/dsu-on-tree.md +++ b/docs/graph/dsu-on-tree.md @@ -45,7 +45,7 @@ void merge(int x, int y) { 直接暴力预处理的时间复杂度为 $O(n^2)$ ,即对每一个子节点进行一次遍历,每次遍历的复杂度显然与 $n$ 同阶,有 $n$ 个节点,故复杂度为 $O(n^2)$ 。 -可以发现,每个节点的答案由其子树何其本身得到,考虑利用这个性质处理问题。 +可以发现,每个节点的答案由其子树和其本身得到,考虑利用这个性质处理问题。 我们可以先预处理出每个节点子树的 $size$ 和它的重儿子,重儿子同树链剖分一样,是拥有节点最多子树的儿子,这个过程显然可以 $O(n)$ 完成 -- 2.11.0