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 nodes and bidirectional edges. That means, you can go from one node to any other node. Every node has some weight . Let's keep it simple and say that for the -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 . Fig - 2 and fig - 3 shows two of the many possible ways to pick tree . Now, you have to do this in a way so that the cost is maximum.
The cost of choosing tree .
For fig -2, the cost is and for fig - 3, the cost is . Neither of the costs are maximum.
The first line contains a single integer () - number of nodes in the tree. Each of the next lines contains two integers and () - denoting an edge of the tree.
Print the maximum possible cost of new tree .
Input | Output |
---|---|
7 2 4 1 2 2 5 3 7 4 7 6 7 | 20 |
Here, tree , marked with bold edges, has two terminals with weight 5 and 6. Number of edges in equals 4. So the cost is , which is the maximum possible cost for this case. |