题意:一颗\(n\)个点的树,定义bud为某个点至少有一个儿子,所有儿子均为叶子结点且这个点不为根,你可以将任意一个bud和它的所有儿子移动到另外一个顶点上,可以操作任意次,问最后的叶子结点数最少是多少.

题解:假如我们将一个bud移到另一个叶子结点上后,bud的父亲变成了一个叶子结点,那么会发现,总叶子结点数是不变的,叶子结点想要减少,就必须满足移动后,bud的父亲不会变成一个叶子结点,很明显,如果bud的父亲是根,那么肯定满足这个条件.所以我们首先把所有bud拆了接到根结点上,那么假设此时的bud数为\(k\),此时的叶子结点数为\(n-k-1\),如果根结点上没有任何儿子是叶子结点,那么先确定一个bud,将的bud依次接到它的叶子结点上,每次叶子结点减少1,一共移动\(k-1\)次,最后答案为\(n-k-1-(k-1)\).如果根结点上有个儿子是叶子结点,那么将\(k\)个bud依次接上去,最后答案为\(n-k-1-k\).具体写法就是dfs,对于一条链,最后一个点一定是叶子结点,叶子结点的父亲是一个bud,bud的父亲是一个叶子结点,就这样分奇偶判断即可.

代码:

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define db double
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}

int u,v;
vector<int> edge[N];
int cnt[N];

void dfs(int u,int fa){
    bool leaf=false;
    for(auto to:edge[u]){
        if(to==fa) continue;
        dfs(to,u);
        if(cnt[to]==1) leaf=true;  //表示这个点的儿子有叶子结点
    }
    if(u!=1){
        if(leaf) cnt[u]=2;
        else cnt[u]=1;
    }
}

int main() {
    #ifdef lr001
        freopen("/Users/somnus/Desktop/data/in.txt","r",stdin);
    #endif
    #ifdef lr002
        freopen("/Users/somnus/Desktop/data/out.txt","w",stdout);
    #endif
    int _;
    scanf("%d",&_);
    while(_--){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;++i) edge[i].clear();
        for(int i=1;i<n;++i){
            scanf("%d %d",&u,&v);
            edge[u].pb(v),edge[v].pb(u);
        }
        dfs(1,-1);
        int flag=0;
        for(auto to:edge[1]){
            if(cnt[to]==1) flag=1;
        }
        ll ans=0;
        for(int i=1;i<=n;++i) ans+=2*(cnt[i]==2);
        printf("%lld\n",n-ans-flag);
    }
    return 0;
}