B、Begginer's Zelda

跳转原题点击此：此题地址

1、题目大意

  给你一个子树，你可任意选择两个节点\(u、v\)，这两个节点之间的所有节点（包括\(u、v\)）都将结合变为一个新的节点。要求你通过该操作将所有的节点变为只有一个节点，求最小的操作数。

2、题目解析

  由题意可得：当\(u、v\)是叶子节点时，可以最大化的合并节点（不用担心合并节点的外面是否有其余的节点）。这样每次操作可以删除两个节点和其路径上的其余节点。所以最终操作数就是叶子节点数量 / 2。
  如果叶子节点数量是奇数，那么最终会多一次操作数量，所以要向上整除。

#include<bits/stdc++.h>

using namespace std;

int t;
int n;

void solve()
{
	cin >> n;
	vector<int>a(n + 1), b(n + 1);
	
	for(int i = 1; i < n; i++)
	{
		int l, r;
		cin >> l >> r;
		a[l]++, b[r]++;
	}
	int ans = 0;
	for(int i = 1; i <= n; i++)
	{
		// 这一步是判断 i 节点是否是叶子节点，因为是无向图
		if( a[i] + b[i] == 1)
			ans++;

	}
	cout << (ans + 1) / 2 << endl;
	
}

int main()
{
	cin >> t;
	while (t--)
	{
		solve();
	}

	return 0;
}