From e5d8bf7ec9e4e40d2dc4ae71d7f0b5bbc73365a1 Mon Sep 17 00:00:00 2001 From: Ir1dXD Date: Thu, 6 Sep 2018 10:47:13 +0800 Subject: [PATCH] update link --- docs/misc/dsu-on-tree.md | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/docs/misc/dsu-on-tree.md b/docs/misc/dsu-on-tree.md index ce51c14a..b98edffe 100644 --- a/docs/misc/dsu-on-tree.md +++ b/docs/misc/dsu-on-tree.md @@ -29,7 +29,7 @@ void merge(int x,int y) 给出一棵树，每个节点有颜色，询问一些子树的颜色数量（颜色可重复）。 -![24620.png](https://oi-wiki.org//misc/images/24620.png) +![24620.png](./images/24620.png) 对于这种问题解决方式大多是运用大量的数据结构（树套树等），如果可以离线，询问的量巨大，是不是有更简单的方法？ @@ -55,7 +55,7 @@ void merge(int x,int y) - 再次遍历其非重儿子及其父亲，用重儿子的 check 对遍历到的节点进行计算，获取整棵子树的 ans； -![24919.png](https://oi-wiki.org//misc/images/24919.png) +![24919.png](./images/24919.png) _上图是一个例子_ @@ -78,7 +78,7 @@ _上图是一个例子_ 又因为如果一个节点是其父亲的重儿子，则他的子树必定在他的兄弟之中最多，所以任意节点到根的路径上所有重边连接的父节点在计算答案是必定不会遍历到这个节点，所以一个节点的被遍历的次数等于他到根节点路径上的轻边树 $+1$（之所以要 $+1$ 是因为他本身要被遍历到），所以一个节点的被遍历次数 $=\log n+1$,总时间复杂度则为 $O(n(\log n+1))=O(n\log n)$，输出答案花费 $O(m)$. -![24909.png](https://oi-wiki.org//misc/images/24909.png) +![24909.png](./images/24909.png) _图中标红的即为重边，重边连向的子节点为重儿子_ -- 2.11.0