Link

CF1905 B Begginer's Zelda

Question

给出一棵树，每次能把一条路径压缩成一个点，求最少几次把树压缩成一个点

Solution

贪心的想，路径肯定越长越好，所以肯定是以一个儿子节点为起点，以一个儿子节点为终点，儿子节点合并了儿子到根的父节点也合并了，每次合并两个儿子节点，假设儿子节点的数量为 \(K\) ，那么最少次数就是 \(\lfloor \frac{K+1}{2} \rfloor\)

Code

#include<bits/stdc++.h>
using namespace std;
int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

vector<int> du;
void solve(){
    int n=read(),ans=0;
    du.assign(n+1,0);
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        du[x]++;du[y]++;
    } 
    for(int i=1;i<=n;i++)
        if(du[i]==1) ans++;
    printf("%d\n",(ans+1)/2);
}
int main(){
    freopen("B.in","r",stdin);
    int T=read();
    while(T--) solve();
    
}