P8552 Rabbit

#include<bits/stdc++.h>
using namespace std;
class solve{
	public:
		int fa[600000+11];
		int Size[600000+11];
		struct node{
			int nt,to;
		}e[600000+11];
		int h[600000+11];
		int ans,cnt,n;
		int find(int x)
		{
			return fa[x]==x?x:fa[x]=find(fa[x]);
		}
		void add(int u,int v)
		{
			e[++cnt]=(node){h[u],v};
			h[u]=cnt;
		}
		void Add(int x,int y)
		{
			x=find(x),y=find(y);
			Size[x]+=Size[y];
			fa[y]=x;
		}
		void work()
		{
			cin>>n;
			for(int i=1; i<=n; i++)
			{
				fa[i]=i;
				Size[i]=1;
				h[i]=0;
			}
			ans=cnt=0;
			for(int i=1,x,y; i<n; i++)//编号大的向编号小的连边 
			{
				cin>>x>>y;
				if(x<y)swap(x,y);
				add(x,y);
			}
			for(int i=1; i<=n; i++)//从编号小的遍历 
			{
				int tot=0;
				for(int K=h[i]; K; K=e[K].nt)//枚举编号小于i且与i有连边的编号j 
				{
					int j=e[K].to;
					int faj=find(j);
					//若编号j被其他编号k搜索过
					//那么j一定可以与编号k所有可到达的编号小于k的没有被标记的编号（一共Size[k]个） 
					//连边 
					if(Size[faj])tot++; 
					Add(i,j);
					//连边 
				}
				if(tot>=2)Size[find(i)]-=3,ans++;
				//三个节点被标记，操作个数加一 
			}
			cout<<ans<<endl;
		}
}x;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		x.work();
	}
	return 0;
}