Edge Strength (Lowe)

0

0 votes
Open, Graph Theory, Depth-first search, Depth First Search, Medium, Algorithms, Graph, Open
Problem

You are given a tree with N nodes and N-1 edges. The tree is rooted at the node 1. Each edge has a strength associated with it.

For an edge i, the strength of the edge is determined as follows:

  • Delete the edge i from the tree.
  • Count the number of unordered pairs of nodes that are no longer connected. The number of pairs is the strength of the edge.

Find the strength of each edge in the tree.

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 N1 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.

Constraints

1N105
1x,yN;x!=y

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the 1st case if we remove the 4th 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.

Editor Image

?