Advertisement
wrequiems

Untitled

Mar 14th, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.84 KB | None | 0 0
  1. n = int(input())
  2.  
  3. graph = {}
  4. for _ in range(n - 1):
  5.     x, y = map(int, input().split(' '))
  6.     graph.setdefault(x, [])
  7.     graph.setdefault(y, [])
  8.     graph[x].append(y)
  9.     graph[y].append(x)
  10.  
  11. subtree = [1] * (n + 1)
  12.  
  13. visited = [False] * (n + 1)
  14.  
  15. def dfs(node):
  16.     if not visited[node]:
  17.         visited[node] = True
  18.         for out in graph[node]:
  19.             if not visited[out]:
  20.                 dfs(out)
  21.                 subtree[node] += subtree[out]
  22.  
  23. dfs(1)
  24.  
  25. for i in range(1, n + 1):
  26.     paths = 0
  27.     nodes_left = subtree[i]
  28.     for out in graph[i]:
  29.         if subtree[i] < subtree[out]:
  30.             paths += subtree[i] * (n - subtree[i])
  31.         else:
  32.             nodes_left -= subtree[out]
  33.             paths += subtree[out] * (nodes_left)
  34.     print('The number of paths that goes through node {} is {}'.format(i, paths))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement