/*
可以推测从叶子结点传送到叶子节点才能使传送次数最少，如果是偶数个叶子结点，那么传送leaf/2次就是答案，如果是奇数个叶子结点，则还有单独一条链需要覆盖
dp[u]表示覆盖完u为根的子树需要走的边数，显然在满足传送次数最少的条件下，dp[u]是可以递推的
设以u为根节点，v是u的儿子，如果v就是叶子结点，那么边u->v算一次
如果v中有奇数个叶子节点，那么边u->v只要算一次，因为偶数个叶子结点可以互相配对，然后剩下的叶子结点会从v延伸到u
如果v中有偶数个叶子结点，那么边u->v要算两次
如果叶子结点是偶数，那么dp[1]就是答案，因为任何一颗子树的偶数对叶子结点互相配对，并可以向上延伸
如果叶子结点时奇数，那么某一个叶子结点只要走到岔路口就可以停止了，不用往上走，所以配对时的向上延伸是不必要的
那么找出这么一个叶子结点：其被多算的向上延伸距离是最大的，那么减去被多算的距离就是最优解
那么如果f是那个额外的叶子结点，f向上走到岔路口，从岔路口一直到根，如果u->v被计算了两次，那么因为f是被外挂出来的，所以可以减去一次，
如果u->v只被算了一次，那么要加一次
*/
#include<bits/stdc++.h> using namespace std; #define maxn 100005 struct Edge{int to,nxt,cnt;}edge[maxn<<1]; int n,ans,leaf,head[maxn],tot; void init(){ memset(head,-1,sizeof head); tot=0; } void addedge(int u,int v){ edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++; } int dfs(int u,int pre){ int cnt=0; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(v==pre)continue; edge[i].cnt=dfs(v,u);//访问子树 cnt+=edge[i].cnt; } ans+=cnt; if(cnt==0)leaf++;//树叶 if(cnt==0||cnt%2)return 1; return 2; } int search(int u,int pre){//返回子树u的最大可以减去的覆盖边数 int mx=0;//一定要初始化！其实在岔路口有不往上延伸的选择！、 for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(v==pre)continue; mx=max(mx,search(v,u)+(edge[i].cnt==2?1:-1)); } return mx; } int main(){ int t,u,v; cin>>t; while(t--){ init(); cin>>n; for(int i=1;i<n;i++){ cin>>u>>v; addedge(u,v); addedge(v,u); } if(n<=2){ printf("%d ",n-1); continue; } int root=1; while(edge[head[root]].nxt==-1) root++;//找到非叶子节点的根 leaf=ans=0; dfs(root,0); if(leaf%2)ans-=search(root,0); printf("%d ",ans); } }