树hackerrank解决错误的故事

Question

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

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

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

Bob 选择一个随机节点作为树的根，并向 Alice 保密所选节点的身份。每个节点被选为根节点的概率相等。
Alice 然后列出 g 个猜测，其中每个猜测的形式为 u v 并且意味着 Alice猜测 parent(v) = u 是真的。保证树中存在连接 u 和 v 的无向边。对于每个正确的猜测，爱丽丝获得一分。如果爱丽丝至少获得 k 分（即她至少 k 的猜测是正确的），她就赢得了比赛。

爱丽丝和鲍勃玩 q 场比赛。给定这棵树、Alice 的猜测以及每场比赛的 k 的值，求出 Alice 赢得比赛的概率，并将其打印在新的一行上，以格式 p/q.

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

问题：无法通过所有测试用例。我对代码进行了健全性测试，没有发现任何问题，但我不知道为什么这在 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)

树hackerrank解决错误的故事

the story of a tree hackerrank solution error

python

algorithm

tree

graph

depth-first-search