Solution

套路题。本题限制条件较多，令人眼花缭乱难以下手，下面展示一下如何拆解问题，对后面的 \rm NOIp 也有帮助。

*2400 的题目花了四十分钟才搞定，可以重开了

• 如果你是 Bob，如何让得分最小？

注意 w 变量完全是没用的，因此目标是 \text{minimize} (n-r-b)(r-b)，也就是 b^2-nb+r(n-r)。这是一个二次函数，因此 Bob 的目的就是让 b 尽量接近 \frac{n}{2}。

还有一个很重要的观察：b 可能得取值范围是 0 到 s 的一个前缀，s 是所有子树中不包含红点的节点个数。显然可以通过构造将这所有数都取到。（如果分析不出这条性质，你会对整个最优化问题都感到头疼，因为你甚至无法直观的得到自变量的取值范围）

• 如果你是 Alice，如何让得分最大？

我们显然要枚举 r。注意 b 的取值范围越小，显然对 Bob 来说更劣，因此我们要让 s 尽可能小。

问题转化为：在树上选 r 个点，覆盖所有点到 1 的路径，使得被覆盖的点个数最多。

• 上述经典问题的解法

假装你不知道这个结论，你应该怎么处理？

首先是进行调整法，得出最优解应当满足的结构，从而获得额外限制。显然，我们选取的点都应当是叶子，否则往下移更优。

考虑分析一下比较小的情况。只选一个叶子，显然选树上的最长链。

如果选了两个叶子，必然有一个是最长链（还是可以通过调整得到）和删去这条链以后得最长链。

对于更多的叶子，显然同理。这个过程就可以刻画为：给你一棵树，每次删掉最长链，记录所有长度。这就是我们熟知的长链剖分。

这个贪心的正确性也是很好保证的：将叶子构成的虚树进行长链剖分，显然所有链的长度都小于等于原树对应排名链的长度，取出对应的链显然更优。使用优先队列维护即可。

综合以上分析，我们就完成了本题。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int n,k,mx[MAXN];
vector<int> G[MAXN];
priority_queue<int> len;
void dfs(int u,int f) {
    vector<int> vc;
    vc.push_back(0);
    for(auto v:G[u]) if(v!=f) dfs(v,u),vc.push_back(mx[v]);
    sort(vc.begin(),vc.end(),[](int A,int B) {
        return A>B; 
    });
    mx[u]=vc[0]+1;
    ffor(i,1,vc.size()-1) len.push(vc[i]);
    return ;
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    ffor(i,1,n-1) {
        int u,v;
        cin>>u>>v,G[u].push_back(v),G[v].push_back(u);  
    }
    dfs(1,0);
    len.push(mx[1]);
    int ans=-n/2*(n-n/2),b=n;
    ffor(r,1,k) {
        if(!len.empty()) b-=len.top(),len.pop();
        if(b<=n/2) ans=max(ans,b*b-n*b+r*(n-r));
        else ans=max(ans,(n/2)*(n/2)-n*(n/2)+r*(n-r));
    }
    cout<<ans;
    return 0;
}