Problem Description

A tree with N nodes and N-1 edges is given. To connect or disconnect one edge, we need 1 unit of cost respectively. The nodes are labeled from 1 to N. Your job is to transform the tree to a cycle(without superfluous edges) using minimal cost.

A cycle of n nodes is defined as follows: (1)a graph with n nodes and n edges (2)the degree of every node is 2 (3) each node can reach every other node with these N edges.

 

Input

The first line contains the number of test cases T( T<=10 ). Following lines are the scenarios of each test case.
In the first line of each test case, there is a single integer N( 3<=N<=1000000 ) - the number of nodes in the tree. The following N-1 lines describe the N-1 edges of the tree. Each line has a pair of integer U, V ( 1<=U,V<=N ), describing a bidirectional edge (U, V).

 

Output

For each test case, please output one integer representing minimal cost to transform the tree to a cycle.

 

Sample Input

 

Sample Output

 

Source

 

Recommend

liuyiding

 

 /* *******************************************

 Author       : kuangbin

 Created Time : 2013年09月08日 星期日 12时00分01秒

 File Name    : 1009.cpp

 ******************************************* */

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #include <stdio.h>

 #include <algorithm>

 #include <iostream>

 #include <string.h>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 using namespace std;

 const int MAXN = ;

 vector<int>vec[MAXN];

 int dp1[MAXN];

 int dp2[MAXN];

 void dfs(int u,int pre)

 {

     int sz = vec[u].size();

     int sum1 = ;

     int maxn = , maxid = -;

     int smaxn = , smaxid = -;

     for(int i = ;i < sz;i++)

     {

         int v = vec[u][i];

         if(v == pre)continue;

         dfs(v,u);

         sum1 += dp2[v]+;

         int tmp = dp1[v] - (dp2[v] + );

         tmp = -tmp;

         if(tmp > smaxn)

         {

             smaxn = tmp;

             smaxid = v;

             if(smaxn > maxn)

             {

                 swap(smaxn,maxn);

                 swap(smaxid,maxid);

             }

         }

     }

     dp1[u] = sum1 - maxn;

     dp2[u] = sum1 - maxn - smaxn;

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     int T;

     int n;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         int u,v;

         for(int i = ;i <= n;i++)

             vec[i].clear();

         for(int i = ;i < n;i++)

         {

             scanf("%d%d",&u,&v);

             vec[u].push_back(v);

             vec[v].push_back(u);

         }

         dfs(,-);

         cout<<dp2[]+<<endl;

     }

     return ;

 }