Limits 1s, 512 MB

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 NN nodes and N1N - 1 bidirectional edges. That means, you can go from one node to any other node. Every node ii has some weight wiw_i. Let's keep it simple and say that wi=iw_i = i for the ii-th 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 AA. Fig - 2 and fig - 3 shows two of the many possible ways to pick tree BB. 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)B = \text{(minimum weight among the terminals of B)} \times \text{(number of edges in B)}.

For fig -2, the cost is minimum(3,4,6)×3=9minimum(3, 4, 6) \times 3 = 9 and for fig - 3, the cost is minimum(1,6)×4=4minimum(1, 6) \times 4 = 4. Neither of the costs are maximum.


The first line contains a single integer NN (1N1000001 ≤ N ≤ 100000) - number of nodes in the tree. Each of the next N1N - 1 lines contains two integers uu and vv (1u,vN1 ≤ u, v ≤ N) - denoting an edge of the tree.


Print the maximum possible cost of new tree BB.


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

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

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


Login to submit.


79% Solution Ratio
mh755628Earliest, Apr '19
steinumFastest, 0.0s
steinumLightest, 16 kB
SrijonKumarShortest, 704B
Toph uses cookies. By continuing you agree to our Cookie Policy.