Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- n = int(input())
- graph = {}
- for _ in range(n - 1):
- x, y = map(int, input().split(' '))
- graph.setdefault(x, [])
- graph.setdefault(y, [])
- graph[x].append(y)
- graph[y].append(x)
- subtree = [1] * (n + 1)
- visited = [False] * (n + 1)
- def dfs(node):
- if not visited[node]:
- visited[node] = True
- for out in graph[node]:
- if not visited[out]:
- dfs(out)
- subtree[node] += subtree[out]
- dfs(1)
- for i in range(1, n + 1):
- paths = 0
- nodes_left = subtree[i]
- for out in graph[i]:
- if subtree[i] < subtree[out]:
- paths += subtree[i] * (n - subtree[i])
- else:
- nodes_left -= subtree[out]
- paths += subtree[out] * (nodes_left)
- print('The number of paths that goes through node {} is {}'.format(i, paths))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement