引言
题目链接：https://codeforces.com/contest/1905/problem/B
思路
题目的合并操作必会将两个叶子结点合并到一起，即减少两个叶子结点，所以只需要算出叶子结点的个数 \(cnt\)，然后 \(\left \lceil \frac{cnt}{2} \right \rceil\) 就是所求的答案。
叶子结点必是只有一条边的点
代码
#include <bits/stdc++.h>
int n;
int u,v;
int cnt;
void solve() {
cnt = 0;
std::map<int,std::vector<int>> mp;
std::cin >> n;
for (int i = 1 ; i <= n - 1 ; i ++ ) {
std::cin >> u >> v;
mp[u].push_back(v);
mp[v].push_back(u);
}
int res = 0;
for (auto [a,b] : mp) {
if(b.size() == 1) {
res ++ ;
}
}
std::cout << (res + 1) / 2 << "\n";
}
int main() {
int t;
std::cin >> t;
while(t -- ) {
solve();
}
return 0;
}