Practice on Toph

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

Afifa's ITS

By kfoozminus · 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 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.

Input

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.

Output

Print the maximum possible cost of new tree B.

Sample

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

    Discussion

    Statistics


    80% Solution Ratio

    mh755628Earliest, Apr '19

    IshtiaqFastest, 0.0s

    mafsofbdLightest, 6.0 MB

    SrijonKumarShortest, 704B

    Submit

    Login to submit

    Editorial

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

    Related Contests

    IUT 10th ICT Fest Programming Contest Ended at 2019-04-13 10:10:00 +0000 UTC
    Replay of IUT 10th ICT Fest Programming Contest Ended at 2019-04-14 18:00:00 +0000 UTC
    SCB-PA Inter School and College Programming Contest 2019 Practice 1 Ended at 2019-09-15 13:05:00 +0000 UTC
    National Girls' Programming Contest 2019 Preliminary Mock Ended at 2019-10-18 15:00:00 +0000 UTC