Two Coins

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given a rooted tree consisting of N nodes. The nodes are numbered from 1 to N, and node 1 is the root. At each node of the tree, you can put zero or one coin such that the following property is satisfied for the tree:
 For each node of the tree, starting from the original configuration, we should be able to get two coins on the node by applying at most two operations of the following kind:
 Take a coin from a node and move it to an adjacent node.
 While trying to get to a particular node, if the same coin is moved in two operations, both those operations should either be towards the root, or both of them should be away from the root. That is, you cannot move a coin to its parent in one operation and then take it to another child of the parent in the second operation.
Find the minimum total number of coins which can be used to get a valid configuration.
Input
The first line of the input contains an integer T.
For each test case, the first line contains an integer N.
Each of the next N  1 lines, contains two space separated integers u, v, denoting that there is an edge between node u and node v of the tree.
Output
For each test case, output a single integer corresponding to the minimum number of coins that can be used. If it's not possible to achieve this, output 1.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 10^{5}
 1 ≤ u, v ≤ N
Subtasks
Subtask #1 (40 points)
 1 ≤ N ≤ 1000
Subtask #2 (60 points)
 Original constraints
Example
Input 2 3 1 2 1 3 5 1 2 1 3 3 4 3 5 Output 3 4
Explanation
Example case 1.
The nodes which have a coin in them are shown by blue color. You can see that each node satisfies the desired property.
Example case 2.
Author:  admin3 
Editorial  https://discuss.codechef.com/problems/TWOCOINS 
Tags  admin3, dynamicprogramming, easymedium, july17, treedp 
Date Added:  5072017 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, 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. 