Code

#include <bits/stdc++.h>
using namespace std;

int solve(vector<vector<int>> &adj) {
    int n = adj.size();
    vector<int> degree(n, 0);
    for (int i = 0; i < n; i++) {
        for (auto child : adj[i]) {
            degree[child]++;
        }
    }

    int leaves_count = 0;
    for (int i = 0; i < n; i++) {
        leaves_count += (degree[i] == 1);
    }

    return (leaves_count + 1) / 2;
}

int main() {
    int t;
    cin >> t;

    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;

        vector<vector<int>> adj(n);
        for (int i = 0; i < (n - 1); i++) {
            int u, v;
            cin >> u >> v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        cout << solve(adj) << "\n";
    }

    return 0;
}