python - 树hackerrank解决错误的故事

Question

Found this problem在 hackerrank 中并且未能通过一些测试用例。

一天，Bob 在一张纸上画了一棵树，有 n 个节点和 n-1 个边。他很快发现节点的父节点取决于树的根。下图显示了一个例子:

得知事实后，鲍勃发明了一个令人兴奋的新游戏，并决定和爱丽丝一起玩。游戏规则如下:

1. Bob 选择一个随机节点作为树的根，并向 Alice 保密所选节点的身份。每个节点被选为根的概率均等。

2. 然后爱丽丝列出了 g 个猜测，其中每个猜测的形式都是 u v 并且意味着爱丽丝猜测 parent(v) =你是真的。保证树中存在连接 u 和 v 的无向边。对于每个正确的猜测，爱丽丝获得一分。如果 Alice 获得至少 k 分(即，她至少 k 的猜测是正确的)，她就赢得了比赛。

Alice 和 Bob 玩q 游戏。给定这棵树、爱丽丝的猜测和每场比赛的 k 值，求出爱丽丝赢得比赛的概率，并将其作为 p/q 格式的约分式打印在新的一行上。

解决方法:有一棵树的一些边缘标有箭头。对于树中的每个顶点，您必须计算有多少箭头指向它。对于一个固定的顶点，这可以通过一个 DFS 来完成。在 DFS 期间以与其自身相反的方向遍历的每个箭头都加 1。如果您知道顶点 v 的答案，则可以在 O(1) 中计算与 v 相邻的顶点 u 的答案。 它与v几乎相同，但是如果有箭头u->v或v->u，它们的贡献是相反的。现在你可以通过移动到第二个DFS中的相邻顶点来使顶点u爬过整个图。

问题:无法通过所有测试用例。我对代码进行了健全性测试，没有发现任何问题，但我不知道为什么这在 hackerrank 平台上不起作用。

import sys

def gcd(a, b):
    if not b:
        return a
    return gcd(b, a%b)

def dfs1(m, guess, root, seen):
    '''keep 1 node as root and calculate how many arrows are pointing towards it'''
    count = 0
    for i in m[root]:
        if seen[i][root] != 1 and seen[root][i] != 1:
            seen[i][root] = 1
            seen[root][i] = 1
            count += (1 if guess[root][i] == 1 else 0) + dfs1(m, guess, i, seen)
    return count

def dfs2(m, guess, root, seen, cost, k):
    '''now make every node as root and calculate how many nodes
       are pointed towards it; If u is the root node for which
       dfs1 calculated n (number of arrows pointed towards the root)
       then for v (adjacent node of u), it would be n-1 as v is the
       made the parent now in this step (only if there is a guess, if
       there is no guess then it would be not changed)'''
    win = cost >= k
    for i in m[root]:
        if seen[i][root] != 1 and seen[root][i] != 1:
            seen[i][root] = 1
            seen[root][i] = 1
            win += dfs2(m, guess, i, seen, cost - (1 if guess[root][i] == 1 else -guess[i][root]), k)
    return win


q = int(raw_input().strip())
for a0 in xrange(q):
    n = int(raw_input().strip())
    m = {}
    guess = [[0 for i in range(n+1)] for i in range(n+1)]
    seen = [[0 for i in range(n+1)] for i in range(n+1)]
    for a1 in xrange(n-1):
        u,v = raw_input().strip().split(' ')
        u,v = [int(u),int(v)]
        if u not in m:
            m[u] = []
        m[u].append(v)
        if v not in m:
            m[v] = []
        m[v].append(u)
    g,k = raw_input().strip().split(' ')
    g,k = [int(g),int(k)]
    for a1 in xrange(g):
        u,v = raw_input().strip().split(' ')
        u,v = [int(u),int(v)]
        guess[u][v] = 1
    cost = dfs1(m, guess, 1, seen)
    seen = [[0 for i in range(n+1)] for i in range(n+1)]
    win = dfs2(m, guess, 1, seen, cost, k)
    g = gcd(win, n)
    print("{0}/{1}".format(win/g, n/g))

Answer 1

一种可能是代码是正确的，但您遇到了堆栈溢出。

可以有 100,000 个节点，如果这些节点全部连接成一条线，您的深度优先搜索递归将失败。

如果这是真的，那么将 DFS 代码从递归公式转换为迭代公式(通过在数组中保留一堆要尝试的东西)应该会有所帮助。

另一种可能性是可能有一个猜测如 1,2 和一个猜测如 2,1。在这种情况下，我不确定分数更新代码是否有效:

win += dfs2(m, guess, i, seen, cost - (1 if guess[root][i] == 1 else -guess[i][root]), k)

也许这样会更好:

win += dfs2(m, guess, i, seen, cost - guess[root][i] + guess[i][root], k)