• + 0 comments

    Python 3 solution:

    #!/bin/python3
    
    import math
    import os
    import random
    import re
    import sys
    from fractions import Fraction
    
    #
    # Complete the 'storyOfATree' function below.
    #
    # The function is expected to return a STRING.
    # The function accepts following parameters:
    #  1. INTEGER n
    #  2. 2D_INTEGER_ARRAY edges
    #  3. INTEGER k
    #  4. 2D_INTEGER_ARRAY guesses
    #
    
    def storyOfATree(n, edges, k, guesses):
        #Write your code here
        adj = [[] for _ in range(n)]
        for u, v in edges:
            u, v = u - 1, v - 1
            adj[u].append(v)
            adj[v].append(u)
    
        guess = set((u - 1, v - 1) for u, v in guesses)
        base = 0
        np = [0] * n
        visit = [False] * n
    
        def rec(node, point):
            nonlocal base
            visit[node] = True
            np[node] = point
            for a in adj[node]:
                if visit[a]:
                    continue
                positive = (node, a) in guess
                negative = (a, node) in guess
    
                if positive and negative:
                    base += 1
                    rec(a, point)
                elif positive:
                    base += 1
                    rec(a, point - 1)
                elif negative:
                    rec(a, point + 1)
                else:
                    rec(a, point)
    
        rec(0, 0)
    
        count = 0
        for p in np:
            if p + base >= k:
                count += 1
    
        if count == 0:
            return "0/1"
        elif count == n:
            return "1/1"
        else:
            return str(Fraction(count, n))
    
    
    if __name__ == '__main__':
        fptr = open(os.environ['OUTPUT_PATH'], 'w')
    
        q = int(input().strip())
    
        for _ in range(q):
            n = int(input().strip())
    
            edges = [list(map(int, input().rstrip().split())) for _ in range(n - 1)]
    
            g, k = map(int, input().rstrip().split())
    
            guesses = [list(map(int, input().rstrip().split())) for _ in range(g)]
    
            result = storyOfATree(n, edges, k, guesses)
    
            fptr.write(result + '\n')
    
        fptr.close()