[C++知识库]Buds Re-hanging

?

?

?

?题意：给定一颗树，定义一种结构为花蕊（有子节点而且子节点都是叶子），能有一种操作把花蕊断开，然后重新拼接后使得叶子节点最少。

题解：把树拆成一个个不能分解的花蕊节点，答案初始为一个根节点，然后每个花蕊的贡献为叶子节点-1，统计所有花蕊的贡献就行了。

#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<cstring>
#include<vector>
#include<set>
#include<cmath>
#include<cstring>
#include<cstdlib>
#define fi first
#define se second
#define u1 (u<<1)
#define u2 (u<<1|1)
#define PII pair<int,int>
#define ll long long
#define ull unsigned long long
#define PLL pair<long long,long long>
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scl(a) scanf("%lld",&a)
#define rep(i,n) for(int i = 0; (i)<(n); i++)
#define rep1(i,n) for(int i = 1; (i)<=(n); i++)
#define pb(a) push_back(a)
#define mst(a,b) memset(a, b, sizeof a)
#define ac cout<<ans<<endl
using namespace std;
vector<int> e[200010];
long long ans;
int dfs(int cur,int fa)
{
    int cnt=0;
    for(auto it:e[cur])
    {
        if(it==fa) continue;
        cnt+=dfs(it,cur);    //儿子是没被断开的话就会返回1
    }
    if(cnt)
    {
        ans+=cnt-1;    //把当前的花蕊连接在根上，贡献为cnt-1
        return 0;   //不返回值了
    }  
    return 1;  //当前节点为下面的节点都断开了
}

void solve()
{
   int n;
   cin>>n;
   for(int i=1;i<=n;i++) e[i].clear();
   ans=1;   //答案初始为1
   for(int i=1;i<n;i++)
   {
       int a,b;
       cin>>a>>b;
       e[a].pb(b);
       e[b].pb(a);
   }
   dfs(1,0);
   ac;
}
int main()
{
    //init();
    int t=1;
    scd(t);
    while(t--) solve();
    return 0;
}