时间戳

首页 > 解决方案 > 算法难题：子树中的不同节点

algorithm - 算法难题：子树中的不同节点

问题描述

我正在尝试解决这个问题：

给定一棵由 n 个节点组成的有根树。节点编号为 1,2,…,n，节点 1 是根。每个节点都有一种颜色。

你的任务是为每个节点确定节点子树中不同颜色的数量。

蛮力解决方案是为每个节点存储一个集合，并在深度优先搜索中累积合并它们。那会运行n^2，效率不是很高。

我如何有效地解决这个（以及同一类问题）？

标签： algorithmtime-complexity

解决方案

首先，您需要将树更改为列表。这种技术通常被称为“Euler Tour”。

基本上，您创建一个空列表并运行 DFS。如果您第一次或最后一次访问节点，请将其颜色推到列表末尾。通过这种方式，您将获得长度为 2 * n 的列表，其中 n 等于节点数。很容易看出，在列表中，与节点的子节点对应的所有颜色都在其第一次和最后一次出现之间。现在，不是树并查询“节点的子树中有多少种不同的颜色”，而是列出并查询“索引 i-th 和 j-th 之间有多少种不同的颜色”。这实际上使事情变得容易得多。

第一个想法——MO的技术O(n sqrt(n))：

我将简要描述一下，我强烈建议搜索 MO 的技术，它在许多资料中都有很好的解释。

按开始对所有查询进行排序（其余的，它们看起来像这样：给定对 (i, j) 查找子数组中从索引 i 到索引 j 的所有不同数字）。制作 sqrt(n) 个桶，将查询从索引 i 开始放置到桶号 i / sqrt(n)。

对于每个存储桶，我们将分别回答查询。按末尾对存储桶中的所有查询进行排序。现在开始使用蛮力处理第一个（最左边的查询）（迭代子数组，将数字存储在 set/hashset/map/whatever 中，获取集合的大小）。

现在要处理下一个，我们将在末尾添加一些数字（下一个查询比前一个更远！），不幸的是，对它的开始做一些事情。我们需要从集合中删除一些数字（如果下一个查询的开始 > 旧查询开始）或从开头添加一些数字（如果下一个查询的开始 < 旧查询开始）。但是，我们也可以使用暴力破解，因为所有查询都从同一段 sqrt(n) 索引开始！总的来说，我们得到 O(n sqrt(n)) 时间复杂度。

第二个想法——检查一下，O(n log n)：是否可以查询 O(lg N) 范围内不同整数的数量？

推荐阅读