Afifa's ITS

kfoozminus Replay of IUT 10th ICT Fe...
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.


80% Solution Ratio
mh755628Earliest, Apr '19
IshtiaqFastest, 0.0s
mafsofbdLightest, 6.0 MB
SrijonKumarShortest, 704B
Toph uses cookies. By continuing you agree to our Cookie Policy.