hackerrankの木の話ハッカーランク解答のエラー

Question

Found this problemいくつかのテストケースを渡すことができませんでした。

一日ボブは、Nノードと紙の上にN-1縁と、ツリーを描きました。彼はすぐにノードの親がツリーのルートに依存することを発見しました。以下の画像は、その一例を示しています。事実を学ぶ

を、ボブはエキサイティングな新しいゲームを考案し、アリスと一緒にプレーすることを決めました。ゲームのルールは以下の通りである：

1. ボブは、ツリーのルートであることを、ランダムなノードを選ぶと、選択したノードのアイデンティティアリスから秘密を保持します。各ノードは、同じ確率でルートとして選択されます。

2. アリスは、各推測フォームでuはをVとアリスは親（V）= Uが真であることが推測された意味グラム推測のリストを作ります。ツリー内にuとvを結ぶ無向枝が存在することが保証されています。 正しい推測のたびに、アリスは1ポイントを獲得します。彼女が少なくともkポイント（つまり、彼女の推測の少なくともkが本当であった）を稼ぐと、アリスはゲームに勝つ。

アリスとボブはQゲームをプレイ。ツリー、アリスの推測、および各ゲームのkの値が与えられれば、アリスがゲームに勝ち、新しい行にp/qの形式で縮小して印刷する確率を見つけます。

解決方法： 矢印が付いたエッジがあるツリーがあります。ツリー内のすべての頂点について、どれくらいの数の矢印がそれを指しているのかを数えなければなりません.1つの固定頂点に対して、これは1つのDFSで行うことができます。 DFS中に横断されたすべての矢印は、それ自身と反対の方向に移動します。1.頂点vの答えを知っていれば、O（1）のvに隣接する頂点uの答えを計算できます。 これはvとほとんど同じですが、矢印u-> vまたはv-> uがある場合、それらの寄与は逆になります。次に、2番目のDFSの隣接する頂点に移動することによって、グラフ全体にわたって頂点をクロールできます。

問題：すべてのテストケースに合格できません。私はコードの健全性テストを行いましたが、問題は見つかりませんでしたが、なぜこれがハッカーランクのプラットフォームで動作していないのか分かりません。

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

1つの可能性は、コードは正しいが、スタックオーバーフローが発生している可能性があります。

ノードは100,000個あります。これらのノードがすべて1つの行に接続されている場合、深さ優先検索再帰は失敗します。

これが当てはまる場合は、DFSコードを再帰的な定式化から（配列の中で試してみるようにスタックしておくことによって）変換することが役立ちます。

もう1つの可能性は、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)