Help needed in solving this problem on graph theory?

general
,
1

given a tree rooted at node 1.The tree has N nodes and N−1 edges. Each edge has some strength associated with it. The strength of an edge is determined by the number of pair of nodes which are connected with the help of that particular edge.

Alternatively consider all the paths between every pair of nodes and the strength of an edge will be equal to the number of paths in which that edge comes.

Monk wants to know the strength of each edge of the tree.

Note: Node pair (i,j) is same as node pair (j,i).

Input Format

First line consists of an integer N denoting the number of nodes in the tree. Then there are 2 integers N-1 and 2.
Then N−1 lines follow. Each line consists of two integers x and y denoting there is an edge between vertex x and vertex y.

Output Format

Output strength of each edge in a separate line. The order of edges in the output should be the same as that in the input.

Sample Input

6
5 2
1 2
2 3
2 4
1 5
5 6

Sample Output

9
5
5
8
5

Explanation

In the 1st case if we remove the edge (1-5) then the node pairs which are not connected are (5,1),(5,2),(5,3),(5,4),(6,1),(6,2),(6,3),(6,4). Hence there are 8 pairs.

2

@vijju123 @mathecodician @meooow @vasja @kauts_kanu @sagar2009kumsr @nvs232 @gkcs

Help me with this problem.

3

If you remove an edge (v, u), where v is nearer to the root as u, then the strength of the edge is size(subtree(u)) \cdot (n - size(subtree(u))).

So for each edge you only need to compute the size of the subtree. That’s a classical problem, that you can solve by doing a dfs. For instance with:

int dfs(int v, int p) {
   int size = 1;
   for (int u :  adj[v]) {
       if (u == p) continue;
       size += dfs(u, v);
   }
   // now size stores the size of the subtree rooted at node v.
   // do something with this information
   return size;
}
2 Likes
4

@afaxnraner

Please can you give me code, it would be really great.

5

@saksham458 I’ve added code with which you can compute the size of each subtree. You now only have to apply the formula I’ve given you.

6

@afaxnraner
can somebody provide the code of above mentioned problem

7

can you explain little more about the formulae size(subtree(u))⋅(n−size(subtree(u)))