algorithm - 计算有向树上的 p-cousins

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

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

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



对于特定的树，问题如下。你得到了多对 (node,p) 并且应该计算(和输出)相应节点的 p-cousins 的数量。

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

解决问题的(渐近)最快方法是什么？

最佳答案

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

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

我们可以将每个查询 (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 ，它在索引 i 存储具有级别 i 的节点数。假设节点 a 在 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 数组中。

关于algorithm - 计算有向树上的 p-cousins，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35450454/