# Sum of Distance

Posted: 11 Mar, 2021
Difficulty: Hard

## PROBLEM STATEMENT

#### Distance between any two nodes is the number of edges between the two given nodes.

##### Input Format:
``````The first line of input contains an integer 'T', the number of test cases.

The first line of the test case contains a single integer ‘N’.

From the second line onwards next 'N-1' lines denote the edges of the graph.

Each edge is characterized by two integers  'A' and 'B' where 'A' and 'B' denote the endpoints of the edge. The edges[i], edges[i] contains the endpoints of edges.
``````
##### Output Format:
``````For each test case, return the list where the ith element denotes the distance of the ith vertex from all others vertices.
``````
##### Note:
``````You are not required to print the expected output; it has already been taken care of. Just implement the function.
``````
##### Constraints
``````1 <= T <= 50
1 <= N <= 10^3
0 <= edges[i], edges[i] <= N-1
Total number of edges = N-1

Time Limit: 1 sec
`````` Approach 1

The key idea is to apply bfs/dfs from each vertex to find distance from all vertices.

Algorithm:

• Create a list answer of size ‘N’ with default value 0.
• Run a for loop from ‘i’ = 0 to ‘N’.Run a bfs from ith vertex such that it will give distance from ith vertex to other vertices.Such that DISTANCE[j] is the distance between ith vertex and jth vertex.
• The ANSWER[i] is equal to sum of distance array.