HeavyLight Decomposition

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given a rooted tree with N nodes. The nodes are numbered from 1 to N, and the root is the node numbered 1. For each node X which is not a leaf, you must choose a node Y which is a child of X and mark the edge between X and Y as heavy (red in the picture below).
Once this has been done, we calculate the cost of each path from the root to a leaf. For this, we decompose the path into segments, where each segment has all light edges or all heavy edges, and each segment is maximal (ie. each segment is as long as possible). So, a path will start with a heavy segment or a light segment, but the segment types will alternate between heavy and light.
The length of a segment is the number of edges in it. The cost of a light segment with length L is L, and the cost of a heavy segment with length L is (ceiling[log_{2}L]+1). The cost of a path from the root to a leaf will be the sum of costs of all the segments.
The decomposition into segments is done independently for each path.
For example:
 The path 1 → 9 contains one heavy segment (1 → 2) with length 1 and one light segment (2 → 9) with length 2, so the cost is (ceiling[log_{2}1]+1) + 2 = (0 + 1) + 2 = 3.
 The path 1 → 17 contains one light segment (1 → 3) with length 1 and one segment (3 → 17) with length 5, so the cost is 1 + (ceiling[log_{2}5]+1) = 1 + (3 + 1) = 5.
 The path 1 → 15 has cost 1 + (ceiling[log_{2}2]+1) + 1 = 1 + (1 + 1) + 1 = 4.
Consider all the paths from the root to leaves. The maximum cost among all these paths, is defined to be the 'cost' of the tree. Different ways of choosing heavy edges can lead to different ‘costs' of the tree.
Please find the minimum ‘cost' of the tree achievable.
Input
 The first line contains one integer, T, the number of test cases. The description of each test case follows:
 The first line of each test case contains one integer, N.
 N1 lines follow, each of which contains two integers a, b. This signifies that there is an edge between nodes a and b.
Output
The output should have only one integer in a new line, the minimum 'cost' achievable.
Constraints
 1 ≤ T ≤ 10
 2 ≤ N ≤ 10^{5}
Subtasks
 Subtask #1 (30 points): 2 ≤ N ≤ 1000
 Subtask #2 (70 points): Original constraints.
Example
Input: 2 12 1 2 2 4 4 5 5 6 4 7 1 3 3 8 8 9 3 10 10 11 10 12 2 1 2 Output: 3 1
Explanation
For first input: one solution is to mark these edges as heavy and the other edges as light: {12, 24, 45, 56, 38, 89, 1011}
Author:  cgy4ever 
Editorial  https://discuss.codechef.com/problems/HLD 
Tags  april17, cgy4ever 
Date Added:  3042017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 