algorithm - 对于树的每个节点，找到最近的祖先节点，使得 val[node] 与 val[ancestor] 互质

Question

对于较短的版本，只阅读紧跟在粗体句子后面的段落 它减少到只有 3 段。
问题说明:给定一个以节点 1 为根的具有 N 个节点的树。每个节点都与一个值相关联。确定包含与当前节点值互质的值的最近祖先。 (注意它是节点值而不是节点号。)
这是我的算法:
将列表定义为: adj[ ] 是邻接列表(从用户获取输入时构建的列表列表)， vis[ ] 表示是否访问了节点， children[ ] 是存储子节点的列表列表每个节点的，当存在时。由于这是一棵树，我们将构造 adj[] 使得 adj[node] = 节点的子节点列表。这有助于我们不用担心节点是否被访问。
创建一个列表 parent[] 来存储每个节点的父节点。这样做:

def search_parent(node):
        for i in adj[node] :
                parent[i] = node
                search_parent(i)

我们的主要算法 是从节点 1 开始并将其标记为 ans[1] = -1，因为它不能有祖先。以DFS方式遍历节点。通过设置变量 v 和 while 循环来检查互素祖先，如果 gcd(node, v) == 1 : ans[node] = v else make v = parent[v]。通过这种方式，我们检查父级是否互质，如果不是，我们检查 parent[parent] 是否互质等，直到我们达到基本情况。
主要问题的伪代码:

ans[1] = -1
parent[1] = 0
def dfs(root) :
        loop node in adj[root] :
                v = root
                while (5 > 0) :
                    if gcd(val[node],val[v]) == 1 :
                        ans[node] = v
                        dfs(node)
                    else :
                        v = parent[v]
                        if v == 0 :
                            ans[node] = -1
                            dfs(node)
               
            

如果我们选择字典父级而不是列表父级，则代码的复杂性可以降低一个常数因子。然后当达到 v = parent[1] 时，我们可以直接使 parent[1] = -1 并且在 while 循环的下一步中返回 ans[node] = -1，然后 while 循环终止。另一方面，当前代码对每个节点通过 if 条件最多 O(depth(node)) 次。
GCD 可以在 O(log_2 max(val[node])) 时间内进行评估。 while 循环的运行时间与 O(depth(node)) 成正比。假设 b 是图的最大分支因子。那么，整体复杂度将为 O(|V| + |E| + sum(b^{r <= d} log_2 max(val[node]))) = O(N log_2 max(val)) .
1. 是否有更优化的代码(平均时间/空间复杂度)？
2. 算法是否正确，或者逻辑中存在漏洞，或者在某些边界情况下？

Answer 1

我把你的算法变成了 Python，所以我可以运行一些测试用例:

from math import gcd

# Example Tree:
# Node numbers     Node values
# (array index or
# dictionary key)
#     0                1
#    / \              / \
#   1   2            7   1
#  / \   \          / \   \
# 3   4   5        14 14   2
#        / \              / \
#       6   7            6   6
adj = [
        [1, 2], # 0
        [3, 4], # 1
        [5],    # 2
        [],     # 3
        [],     # 4
        [6, 7], # 5
        [],     # 6
        []      # 7
]

val = [1, 7, 1, 14, 14, 2, 6, 6]

parent = [-1, 0, 0, 0, 0, 0, 0, 0]

def search_parent(node):
    for i in adj[node]:
        parent[i] = node
        search_parent(i)

search_parent(0)

ans = [-1, 0, 0, 0, 0, 0, 0, 0]

def dfs(root):
    for node in adj[root]:
        a = None
        v = root
        while a is None:
            if gcd(val[node], val[v]) == 1: % coprime
                a = v
                break
            else: % not coprime
                v = parent[v]
                if v == 0:
                    a = -1
                break
        ans[node] = a

        if node != 0:
            dfs(node) # continuing dfs no matter whether it's coprime or not.

dfs(0)

print("Nodes:   {0}".format(list(range(0,8))))
print("Values:  {0}".format(val))
print("Parents: {0}".format(parent))
print("Answers: {0}".format(ans))

问题 2:正确性
因此，关于问题 2(正确性)，让我们考虑一些测试用例 - 尽管可能只是我不明白您的期望。
如果所有值都具有平凡值 1那么最接近的互质总是父:

Nodes:   [0, 1, 2, 3, 4, 5, 6, 7]
Values:  [1, 1, 1, 1, 1, 1, 1, 1]
Parents: [-1, 0, 0, 1, 1, 2, 5, 5]
Answers: [-1, 0, 0, 1, 1, 2, 5, 5]

现在考虑不是 parent 而是祖 parent 是祖先的情况。在分支2的情况下这看起来正确，但不适用于分支 1其中它的子节点互质的节点是根节点，遇到特殊情况 if v == 0: a = -1 :

Nodes:   [0, 1, 2, 3, 4, 5, 6, 7]
Values:  [1, 7, 1, 14, 14, 2, 6, 6]
Parents: [-1, 0, 0, 1, 1, 2, 5, 5]
Answers: [-1, 0, 0, -1, -1, 2, 2, 2]

我想你宁愿期待 if v == 0: a = 0这里:

Answers: [-1, 0, 0, 0, 0, 2, 2, 2]

但是，您最初想到的情况是根节点是互质的，其中 if v == 0: a = -1是正确的:

Nodes:   [0, 1, 2, 3, 4, 5, 6, 7]
Values:  [7, 7, 1, 14, 14, 2, 6, 6]
Parents: [-1, 0, 0, 1, 1, 2, 5, 5]
Answers: [-1, -1, 0, -1, -1, 2, 2, 2]

所以这两种情况可能需要区分。
问题 1:复杂性
关于复杂性，您似乎计算错了 - 我认为您不能将父查找的成本添加到深度优先搜索的成本中。因为您必须为每个节点进行父查找。
问题是您将使用 for 向下传递到后代。与while一起去见祖先.如果您想要任何改进，您必须选择一个方向，例如仅向下传递 for 的后代，并计算传递给对 dfs 的调用的中间值.
但是，我认为您无法摆脱 while循环，你只能在最好的情况下减少它。例如，您可以通过添加 node 来构建相关祖先的列表，而不是递归所有祖先。仅当 val[v] % val[node] == 0 时才加入列表并删除 v从列表中如果 val[node] % val[v] == 0在递归调用 dfs 之前.
可能不值得(虽然没有进行任何测试)。