Last Updated: 24 Mar, 2021

Sum Of Node Distances

Moderate

Asked in companies

Solve now

Problem statement

You have been given an array/list ‘EDGES’ of size (N - 1) x 2 representing the undirected connected tree with ‘N’ nodes from 0…’N’ - 1 and ‘N’ - 1 edges such that the i’th edge connects ‘EDGES[i][0]’ node with ‘EDGES[i][1]’ node.

You need to print an array/list ‘ANS’, where ANS[i] is the sum of the distances between node ‘i’ and all other nodes.

For example:

For ‘N’ = 6 and ‘EDGES’ = [ [0,1], [0, 2], [2, 3], [2, 4], [2, 5] ], see the below picture for reference:

1. For node 0:
   a. Distance from node 0 to node 1 is 1.
   b. Distance from node 0 to node 2 is 1.
   c. Distance from node 0 to node 3 is 2.
   d. Distance from node 0 to node 4 is 2.
   e. Distance from node 0 to node 5 is 2.
   So the sum of all the distances is 8.

2. For node 1:
   a. Distance from node 1 to node 0 is 1.
   b. Distance from node 1 to node 2 is 2.
   c. Distance from node 1 to node 3 is 3.
   d. Distance from node 1 to node 4 is 3.
   e. Distance from node 1 to node 5 is 3.
   So the sum of all the distances is 12.

3. For node 2:
   a. Distance from node 2 to node 0 is 1.
   b. Distance from node 2 to node 1 is 2.
   c. Distance from node 2 to node 3 is 1.
   d. Distance from node 2 to node 4 is 1.
   e. Distance from node 2 to node 5 is 1.
   So the sum of all the distances is 6.

4. For node 3:
   a. Distance from node 3 to node 0 is 2.
   b. Distance from node 3 to node 1 is 3.
   c. Distance from node 3 to node 2 is 1.
   d. Distance from node 3 to node 4 is 2.
   e. Distance from node 3 to node 5 is 2.
   So the sum of all the distances is 6.

5. For node 4:
   a. Distance from node 4 to node 0 is 2.
   b. Distance from node 4 to node 1 is 3.
   c. Distance from node 4 to node 2 is 1.
   d. Distance from node 4 to node 3 is 2.
   e. Distance from node 4 to node 5 is 2.
   So the sum of all the distances is 6.

6. For node 5:
   a. Distance from node 5 to node 0 is 2.
   b. Distance from node 5 to node 1 is 3.
   c. Distance from node 5 to node 2 is 1.
   d. Distance from node 5 to node 3 is 2.
   e. Distance from node 5 to node 4 is 2.
   So the sum of all the distances is 6.

So, ‘ANS’ for the above example will be [8, 12, 6, 10, 10, 10].

Input Format

The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.

The first line of each test case contains an integer ‘N’ representing the number of nodes in the tree.

The next ‘N’ - 1 lines of each test case contains two single space separated integers denoting ‘EDGES[i][0]’ and ‘EDGES[i][1]’.

Output Format :

For each test case, print a single line containing space-separated integers denoting the sum of distances of each node from a node.

The output for each test case is printed in a separate line.

Note:

You don't have to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 100
1 <= N <= 10 ^ 4
0 <= EDGE[i][0] and EDGE[i][1] < N

Time limit: 1 sec

Solve now

Approaches

01 Approach

We can find the distance from a node from all other nodes in linear time. If we move our root from one node to its connected node, then one part of the node gets closer, and the other part gets further.

We try to find how many nodes are in both the parts, and then we can solve this problem. In one single traversal in the tree, we should get enough information for it and don't need to do it repeatedly.

As shown in the picture below, the answer for node ‘A’ subtree is 3 and answer for ‘B’ subtree is 6. Now if you observe carefully for the whole tree, the ‘ANS[A]’ = ‘ANS[A]’(subtree) + ‘ANS[B]’(subtree) + number of nodes in ‘B’ subtree. We use this observation to find our ‘ANS’ list/array in linear time.

Here is the complete algorithm:

Make the undirected graph ‘TREE’ using given ‘EDGES’.
Make an array/list ‘count’ initialize it with 1, an array/list ‘result’ initialized with 0.
Call our ‘DFS_UTIL1’ function and pass 0’th node and -1 as its parent. The ‘DFS_UTIL1’ function is explained below:
- For each neighbor of the current node do the following:
  - Call ‘DFS_UTIL1’ function for all the neighbors of the current node.
  - After the call update ‘count[node]’ = ‘count[node]’ + ‘count[neighbour]’.
  - Update ‘result’ as ‘result[node]’ = ‘result[node]’ + ‘result[neighbour]’ + ‘count[neighbour]’.
Now Call ‘DFS_UTIL_2’ and pass 0 as root and -1 as the parent of the root. ‘DFS_UTIL_2’ function is explained below:
- For each neighbour of the current node do the following:
  - Update ‘result[neighbour]’ = ‘res[node]’ + ‘count[neighbour]’ + ‘N’ - ‘count[neighbour]’.
  - Call ‘DFS_UTIL2’ function for all the neighbors of the current node.
Finally, return ‘result’.

Solve now