Found this problem在 hackerrank 中并且未能通过一些测试用例。
一天，Bob 在一张纸上画了一棵树，有 n 个节点和 n-1 个边。他很快发现节点的父节点取决于树的根。下图显示了一个例子:
得知事实后，鲍勃发明了一个令人兴奋的新游戏，并决定和爱丽丝一起玩。游戏规则如下:
Bob 选择一个随机节点作为树的根，并向 Alice 保密所选节点的身份。每个节点被选为根的概率均等。
然后爱丽丝列出了 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))
最佳答案
一种可能是代码是正确的，但您遇到了堆栈溢出。
可以有 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)
关于python - 树hackerrank解决错误的故事，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44840604/