题解：P15268 「UTOI 1C」Delirium Of Aeons

· · 题解

Solution

假设 n=m，答案显然就是叶子的个数。

现在 m<n，我们需要割断 m-1 条边，也就是要保留 n-1-(m-1)=n-m 条边。现在我们可以将一些叶子节点合并到主干上，以减少叶子数量（其实就是不合并叶子节点的那一条链一直到分叉口，这样这一条链就至少与其他两个树上块状物相连，叶子就消掉了）。

Subtask 3 启示我们答案至少为一条链，也就是 2。

如果叶子要合并到主干上，也就是从叶子节点到主干的那些边都得保留，也就是说会消耗 n-m 的那些能保留的边。所以我们贪心地从小到大选叶子结点的那一条路径合并。

我们来思考一下主干是什么。对于一棵树，显然是树的直径。对于树上的其他枝条，显然也有着属于这个枝条的树的直径。也就是说，树的枝条要合并到树的直径上，树的枝条上的小枝叶要合并到对应的枝条上。

这些部分有点难懂。大家可以停下来慢慢思考一下。总结一下就是叶子要合并到最长的主干上，代价就是叶子到主干的距离。可以参考一下代码实现。

:::success[code]


#include <bits/stdc++.h>
using namespace std;
int T,n,m,u,v,d[200005],ans,maxn,maxu;
vector<int> edge[200005],len;
int dfs(int u,int p,int root){
    vector<int> l;
    for(auto to:edge[u])
        if(to!=p)
            l.push_back(dfs(to,u,root));
    sort(l.begin(),l.end(),greater<int>());
    int tmp=u==root?2:1;
    for(int i = 0;i<l.size();i++)
        if(i>=tmp) len.push_back(l[i]);
    if(l.size()) return l[0]+1;
    return 1;
}
void dfss(int u,int p,int k){
    if(k>maxn) maxn=k,maxu=u;
    for(auto to:edge[u]) if(to!=p) dfss(to,u,k+1);
}
void solve(){
    cin>>n>>m;
    fill(d+1,d+1+n,0),ans=maxn=maxu=0,len.clear();
    for(int i = 1;i<=n;i++) edge[i].clear();
    for(int i = 1;i<n;i++)
        cin>>u>>v,
        edge[u].push_back(v),
        edge[v].push_back(u),
        d[u]++,d[v]++;
    for(int i = 1;i<=n;i++) ans+=d[i]==1;
    dfss(1,0,0);
    dfs(maxu,0,maxu);
    sort(len.begin(),len.end());
    int cnt=n-m;
    for(auto t:len)
        if(cnt>=t) cnt-=t,ans--;
        else break;
    cout<<ans<<'\n';
}
int main(){
    cin>>T;
    while(T--) solve();
    return 0;
}