Limits 1s, 512 MB

What is a tree?

A tree is a bidirectional connected graph with no cycle.

In a tree, we can create exactly one cycle if we connect any two nodes by an edge. Professor Ratman thinks that the cycle has holy powers. So the cost of such one cyclic graph is the total distance from all the nodes to any node of the cycle. Professor Ratman wants to determine the minimum cost given that you can connect any two nodes of the tree.

So you have to minimize (distance from every node to the cycle)\sum(\text{distance from every node to the cycle})

Suppose, we have the following tree:

If we connect 2 and 6 and make a cycle, then the cost would be 1 + 1 + 2 = 4.

But, if we connect 4 and 6, the cost will be, 1 + 1 = 2, which is the minimum cost in this case.

Your job is to find the minimum cost of creating one cycle.


The first line will contain an integer T(1T10)T ( 1 \leq T \leq 10), the number of test cases.

For each test case, the first line contains n(1n105)n (1 \leq n \leq 10^5), the number of nodes in the tree.

Next n1n-1 lines will describe the tree. Each line will contain two space-separated integers uu and v(1u,vn)v (1 \leq u, v \leq n) indicating that there is a bidirectional edge between uu and vv.

It is guaranteed that the input is a valid tree and the sum of nn over all test cases will not exceed 3×1053\times10^5, that means t=1T(n)3×105\sum\limits_{t=1}^{T}(n) \leq 3\times10^5.


For each test case, print “Case X: Y” where “X” indicates the case number and “Y” indicates the minimum cost for the given case.


1 5
5 2
5 6
3 5
3 4
Case 1: 2


Login to submit.


59% Solution Ratio
tasmeemrezaEarliest, Jan '23
Mushfiqur05Fastest, 0.1s
amirhozaifaLightest, 15 MB
ashraful9194Shortest, 1281B
Toph uses cookies. By continuing you agree to our Cookie Policy.