codeforces B. Begginer‘s Zelda

分析

• 因为最后要化成一个节点，所以每一次选择两个点最理想化的是选择两个叶子节点。所以就变成询问叶子节点的数量。
• 无论奇偶数个叶子节点要选 $(n+1)/2$ 次。

思路

• 无向图记录节点的度，如果度为 $1$ 则是叶子节点。

Think Twice, Code Once

#include <bits/stdc++.h>
#define il inline
#define get getchar
#define put putchar
#define is isdigit
#define int long long
#define dfor(i,a,b) for(int i=a;i<=b;++i)
#define dforr(i,a,b) for(int i=a;i>=b;--i)
#define dforn(i,a,b) for(int i=a;i<=b;++i,put(10))
#define mem(a,b) memset(a,b,sizeof a)
#define memc(a,b) memcpy(a,b,sizeof a)
#define pr 114514191981
#define gg(a) cin<<a,put(32)
#define INF 0x7fffffff
#define tt(x) cin<<x<<'\n'
#define endl '\n'
#define ls i<<1
#define rs i<<1|1
#define la(r) tr[r].ch[0]
#define ra(r) tr[r].ch[1]
#define lowbit(x) (x&-x)
#define ct cin.tie(nullptr),ios_base::sync_with_stdio(false)
using namespace std;
typedef unsigned int ull;
typedef pair<int, int> pii;
int read(void) {
    int x=0,f=1;char c=get();
    while(!is(c)) (f=c==45?-1:1),c=get();
    while(is(c)) x=(x<<1)+(x<<3)+(c^48),c=get();
    return x*f;
}
void write(int x) {
    if (x < 0) x = -x, put(45);
    if (x > 9) write(x / 10);
    put((x % 10) ^ 48);
}
#define writeln(a) write(a), put(10)
#define writesp(a) write(a), put(32)
#define writessp(a) put(32), write(a)
const int N = 1e5 + 10, M = 1e5 + 10, SN = 1e3 + 10, mod = 998244353;
signed main() {
    int T = read();
    while (T--) {
        int n = read();
        vector<int> in(n + 1);
        for (int i = 1; i < n; ++i) {
            int u = read(), v = read();
            ++in[u], ++in[v];
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) ans += in[i] == 1;
        writeln((ans + 1) >> 1);
    }
    return 0;
}