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.
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;
}
@afaxnraner
I think it’s too late, but I need some help from you. I have seen this problem in HackerEarth recently and this is the link Edge Strength Problem. I tried the approach that is suggested by you. But unfortunately, I got “Memory limit exceed” and “Time Limit Exceed” errors.
Can you please help me in trying this problem after a long time?
Hope you will.