fork download 
  1. #!/bin/python
  2.  
  3. import sys
  4.  
  5. def gcd(a, b):
  6.     if not b:
  7.         return a
  8.     return gcd(b, a%b)
  9.  
  10. def dfs1(m, guess, root, seen):
  11.     count = 0
  12.     stack = []
  13.     stack.append(root)
  14.     while len(stack):
  15.         root = stack.pop(len(stack)-1)
  16.         for i in m[root]:
  17.             if seen[i][root] != 1 and seen[root][i] != 1:
  18.                 seen[i][root] = 1
  19.                 seen[root][i] = 1
  20.                 count += (1 if guess[root][i] == 1 else 0)
  21.                 stack.append(i)
  22.     return count
  23.  
  24. def dfs2(m, guess, root, seen, cost, k):
  25.     stack = []
  26.     stack.append((root, cost))
  27.     t_win = 0
  28.     while len(stack):
  29.         (root, cost) = stack.pop(len(stack)-1) 
  30.         t_win += cost >= k
  31.         for i in m[root]:
  32.             if seen[i][root] != 1 and seen[root][i] != 1:
  33.                 seen[i][root] = 1
  34.                 seen[root][i] = 1
  35.                 stack.append((i, cost - guess[root][i] + guess[i][root]))
  36.     return t_win
  37.  
  38.  
  39. q = int(raw_input().strip())
  40. for a0 in xrange(q):
  41.     n = int(raw_input().strip())
  42.     m = {}
  43.     guess = [[0 for i in range(n+1)] for i in range(n+1)]
  44.     seen = [[0 for i in range(n+1)] for i in range(n+1)]
  45.     for a1 in xrange(n-1):
  46.         u,v = raw_input().strip().split(' ')
  47.         u,v = [int(u),int(v)]
  48.         if u not in m:
  49.             m[u] = []
  50.         m[u].append(v)
  51.         if v not in m:
  52.             m[v] = []
  53.         m[v].append(u)
  54.     g,k = raw_input().strip().split(' ')
  55.     g,k = [int(g),int(k)]
  56.     for a1 in xrange(g):
  57.         u,v = raw_input().strip().split(' ')
  58.         u,v = [int(u),int(v)]
  59.         guess[u][v] = 1
  60.     #print(m)
  61.     #for i in guess:
  62.     #    print i
  63.     cost = dfs1(m, guess, 1, seen)
  64.     #print("cost", cost)
  65.     seen = [[0 for i in range(n+1)] for i in range(n+1)]
  66.     win = dfs2(m, guess, 1, seen, cost, k)
  67.     #print(win, n)
  68.     g = gcd(win, n)
  69.     print("{0}/{1}".format(win/g, n/g))
Runtime error #stdin #stdout #stderr 0.01s 23288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
Traceback (most recent call last):
  File "prog.py", line 39, in <module>
EOFError: EOF when reading a line
https://ideone.com/9xJC3a
language:
Python (cpython 2.7.16)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!