【南外】DPS1-C-526互联

/*
树形DP，记 f[i] 表示覆盖以 i 为根的子树最少需要链的数量。
记 fl[i]=0/1 表示当前 i 节点是否属于任意一条链。
记 res 表示当前搜到节点 x 时，它有多少个儿子还不属于任何一条链。
考虑贪心（不太会证明正确性） 
如果当前节点的 res>=2，则可以选两个未连节点与 x 共同构成一条链，fl[x]=1，f[x]-=2
否则，如果当前节点的 res=1，则可以选一个未连节点单独构成一条链，f[x]-=1
res=1 中不把 x 连进去的原因是，给他的父亲多留 res，最终答案一定不劣。 
*/ 

//If, one day, I finally manage to make my dreams a reality...
//I wonder, will you still be there by my side?
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define int long long
#define y1 cyy
#define fi first
#define se second
#define cnt1(x) __builtin_popcount(x)
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lbt(x) (x&(-x))
using namespace std;
int T,n,u,v,f[200005]; 
bool fl[200005];
vector<int> a[200005];
void dfs(int x,int fa){
	f[x]=1;
	int res=0;
	for(auto tmp:a[x]){
		if(tmp==fa) continue;
		dfs(tmp,x);
		f[x]+=f[tmp];
		if(!fl[tmp]) res++;
	}
	if(res>=2) fl[x]=1,f[x]-=2;
	else if(res==1) f[x]--;
}
signed main(){
	IOS;TIE;
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++){
			a[i].clear();
			fl[i]=f[i]=0;
		}
		for(int i=1;i<n;i++){
			cin>>u>>v;	
			a[u].pb(v),a[v].pb(u);
		}
		dfs(1,0);
		cout<<f[1]<<endl;
	}
	return 0;
}