Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Imagine some made up story here including Afifa (my little sister) and an Intelligent Transport System, which ultimately leads to the main problem.

You are given a connected tree containing **N** nodes and **N - 1** bidirectional edges. That means, you can go from one node to any other node. Every node **i** has some weight **wi**. Let's keep it simple and say that **wi = i** for the **ith** node. Let this tree be called A.

Let's call a node **terminal** if it has one edge attached to it or no edge at all.

You have to pick a "part" of this tree that's also a tree. You can pick the entire tree as well. Let this new tree be called B.

**fig - 1** denotes an example of tree **A**. **fig - 2** and **fig - 3** shows two of the many possible ways to pick tree **B**. Now, you have to do this in a way so that the cost is maximum.

The cost of choosing tree B = ( minimum weight among the terminals of B ) * ( number of edges in B )

For fig -2, cost is minimum(3, 4, 6) * 3 = 9 and for fig - 3, cost is minimum(1, 6) * 4 = 4. Please note that neither of the costs are maximum.

The first line contains a single integer **N (1 ≤ N ≤ 100000)** - number of nodes in the tree.

Each of the next **N - 1** lines contains two integers **u** and **v (1 ≤ u, v ≤ N)** - denoting an edge of the tree.

Print the maximum possible cost of new tree **B**.

Input | Output |
---|---|

7 2 4 1 2 2 5 3 7 4 7 6 7 | 20 |

**Sample I/O Explanation:**

Here, tree B, marked with bold edges, has two terminals with weight 5 and 6. Number of edges in B equals 4.

So cost is minimum(5, 6) * 4 = 20, which is the maximum possible cost for this case.

80% Solution Ratio

mh755628Earliest,

IshtiaqFastest, 0.0s

mafsofbdLightest, 6.0 MB

SrijonKumarShortest, 704B

Login to submit

First, take the whole tree A as B. For this, cost would be minimum weight among terminals * n - 1. L...

Toph uses cookies. By continuing you agree to our Cookie Policy.