4

我们得到了一个可以使用的有向树。我们将p-ancestor和p-cousin的概念定义如下

p-ancestor：如果一个节点是另一个节点的父节点，则它是另一个节点的1-祖先。如果它是第(p-1) 个祖先的父节点，则它是节点的p 祖先。

p-cousin：一个节点是另一个节点的p-cousin，如果它们共享相同的p-ancestor。

例如，考虑下面的树。

例子

4 有三个 1 表兄弟，即 3、4 和 5，因为它们都共享共同的 1 祖先，即 1

对于特定的树，问题如下。您将获得多对 (node, p ) 并且应该计算（并输出）相应节点的p-cousin的数量。

一个缓慢的算法是爬到p 祖先并为每个节点运行 BFS。

解决问题的（渐近）最快的方法是什么？

4

3 回答 3

1

如果可以接受离线解决方案，则两次深度优先搜索就可以完成这项工作。

假设我们可以索引所有从 0 到 n - 1的n查询(node, p)

我们可以将每个查询(node, p)转换为另一种类型的查询(ancestor , p)，如下所示：

查询的答案(node, p)，节点有级别a（从根到此节点的距离是a），是级别a的祖先的后代级别的数量a - p。因此，对于每个查询，我们都可以找到那个祖先是谁：

伪代码

dfs(int node, int level, int[]path, int[] ancestorForQuery, List<Query>[]data){
    path[level] = node;
    visit all child node;
    for(Query query : data[node])
       if(query.p <= level)
          ancestorForQuery[query.index] = path[level - p];
}

现在，在第一个 DFS 之后，我们有一个新类型的查询，而不是原来的查询(ancestor, p)

假设我们有一个数组count，它在 index 处i存储了具有 level 的节点的数量i。假设a在 level的节点x，我们需要计算p后代的数量，所以，这个查询的结果是：

query result = count[x + p] after we visit a -  count[x + p] before we visit a

伪代码

dfs2(int node, int level, int[] result, int[]count, List<TransformedQuery>[]data){
   count[level] ++;
   for(TransformedQuery query : data[node]){
         result[query.index] -= count[level + query.p];
   }
   visit all child node;
   for(TransformedQuery query : data[node]){
         result[query.index] += count[level + query.p];
   }
}

每个查询的结果存储在result数组中。

于 2016-02-17T08:41:45.773 回答
0

如果 p 是固定的，我建议使用以下算法：

假设 count[v] 是 v 的 p-children 的数量。最初所有 count[v] 都设置为 0。pparent[v] 是 v 的 p-parent。

现在让我们在树上运行一个 dfs 并保留访问节点的堆栈，即当我们访问某个 v 时，我们将其放入堆栈中。一旦我们离开 v，我们就会弹出。

假设我们已经到了 dfs 中的某个节点 v。让我们做count[stack[size - p]]++，说明我们是v的p-child。还有pparent[v] = stack[size-p]

一旦你的 dfs 完成，你可以像这样计算所需的 v 的 p-cousins 数量：count[pparent[v]]

dfs 的复杂度为 O(n + m)，每个查询的复杂度为 O(1)

于 2016-02-17T08:39:12.510 回答
0

首先，我将描述一种相当简单的方法来在 O(p) 时间内回答每个查询，该方法使用 O(n) 预处理时间和空间，然后提到一种可以将查询时间加速到 O(log p) 时间的方法只是 O(log n) 额外预处理时间和空间的一个因素。

O(p)-时间查询算法

基本思想是，如果我们写出在树的 DFS 遍历期间访问的节点序列，使得每个节点都写在与其在树中的级别相对应的垂直位置，那么 p-cousins 的集合图中的一个节点构成一个水平区间。请注意，这个“写出”看起来非常像典型的树形图，除了没有连接节点的线，并且（如果使用后序遍历；前序也一样好）父节点总是出现在其子节点的右侧。所以给定一个查询 (v, p)，我们要做的基本上是：

  1. 找到给定节点 v 的第 p 个祖先 u。这需要 O(p) 时间。
  2. 找到u的第p个左后裔l——也就是你重复访问当前节点最左边子节点的过程，p次后到达的节点。天真地这需要 O(p) 时间。
  3. 找到 u 的第 p 个右后裔 r（定义类似）。天真地这需要 O(p) 时间。
  4. 返回值 x[r] - x[l] + 1，其中 x[i] 是一个预先计算的值，记录上述序列中与, 节点 i。这需要恒定的时间。

预处理步骤是我们为每个 1 <= i <= n 计算 x[i] 的地方。这是通过执行构建第二个数组 y[] 的 DFS 来实现的，该数组记录到目前为止在深度 d 处访问的节点数 y[d]。具体来说，对于每个 d，y[d] 初始为 0；在 DFS 期间，当我们访问深度为 d 的节点 v 时，我们只需增加 y[d]，然后设置 x[v] = y[d]。

O(log p)-时间查询算法

如果树相当平衡，上述算法应该已经足够快了——但在最坏的情况下，当每个节点只有一个子节点时，O(p) = O(n)。请注意，在上述 4 个步骤中的前 3 个步骤中，它在树上上下导航，这会强制 O(p) 时间——最后一步需要恒定时间。

为了解决这个问题，我们可以添加一些额外的指针来更快地在树上上下导航。一种简单灵活的方式使用“指针加倍”：对于每个节点 v，我们将存储 log2(depth(v)) 指向连续更高祖先的指针。为了填充这些指针，我们执行 log2(maxDepth) DFS 迭代，在第 i 次迭代中，我们将每个节点 v 的第 i 个祖先指针设置为其第 (i-1) 个祖先的第 (i-1) 个祖先：每个 DFS 的每个节点只需要两次指针查找。使用这些指针，在树上移动任何距离 p 总是最多需要 log(p) 次跳跃，因为每次跳跃时距离至少可以减少一半。完全相同的过程可用于填充“左后裔”和“右后裔”的相应指针列表，以分别将步骤 2 和 3 加速到 O(log p) 时间。

于 2016-02-22T16:16:03.630 回答