You are viewing a single comment's thread. Return to all comments →
Python 3:
def dfs(v, adj_list, parent): for u in adj_list[v]: if u != parent[v]: parent[u] = v dfs(u, adj_list, parent) def sum_dfs(v, p, adj_list, count, k): count[v] += int(p != -1) * count[p] out = count[v] >= k for u in adj_list[v]: if u != p: out += sum_dfs(u, v, adj_list, count, k) return out def storyOfATree(n, edges, k, guesses): adj_list = {i:set() for i in range(n)} for u, v in edges: adj_list[u-1].add(v-1) adj_list[v-1].add(u-1) parent, count = [0]*n, [0]*n dfs(0, adj_list, parent) for u, v in guesses: if parent[v-1] == u-1: count[0] += 1 count[v-1] -= 1 else: count[u-1] += 1 n_correct = sum_dfs(0, -1, adj_list, count, k) out = Fraction(n_correct, n) return f"{out.numerator}/{out.denominator}"
Seems like cookies are disabled on this browser, please enable them to open this website
The Story of a Tree
You are viewing a single comment's thread. Return to all comments →
Python 3: