E - Purple Crayon

一个初始全部为空白节点的树。红（先手）蓝两方轮流对其染色：（注：以下操作可以进行任意次）

• 红：选择一个空白子树将其全部染为红色。（注：一回合染色的节点数不能超过k）
• 蓝：选择任意个空白子树将其全部染为蓝色。（染色数无限制）

定义val = w(r-b) ，w：空白节点，r：红色，b：蓝色。

红方想让val最大化，蓝方想让b最小化。求双方均采取最优策略的情况下的val。

$val = (n-r-b)(r-b) = r(n-r)-b(n-b)$

首先对于蓝方来说，只需要最大化b(n-b) ，即选尽可能多的节点。

红方先选：

• k >= 叶 把所有叶节点全选了使得b=0。此时 val = r(n-r)。显然r接近2/n时最小。即$r = max(min(2/n, k),叶)$

• k < 叶 即此时红方没有办法保证蓝方无点可选，显然选择一个叶节点后可以叶 -> 根上的所有路径全部被染色。因此问题变成了求选k个点尽可能多的染色。根据官方题解的做法，我们可以先求出每个点的深度，降序排序后dfs。到达根或一个已染色的节点后返回这条链的长度。将链长降序排序后选择最大的k个即可。

  之后剩下的就只能由蓝方任意选择了，如果剩下的所有点<=2/n则全选，如果 > 2/n ，则只需选 2/n个即可。因为b = 2/n时使得结果最小化，且r再选只会使结果更小。（因为已经是负值了）

关于求这样的链长除了染色以外，从dmyls那里学习的另一种做法如下：

mx[u] 表示 u 到最底端的链长。每次遍历到u时，将所有的mx[v]存进一个vector中，最大的作为u的链继续向上延伸，其余的加入最后统计的链长里即可。

非常妙www，虽然会因为排序操作使时间复杂度变大，但毫无影响。

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define mod 998244353
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
using namespace std;
const int maxn = 200005;
/**/
int n, k, mx[maxn], r, b;
vi eg[maxn];
vi cur;
/**/
void dfs(int u, int fa)
{
	if(eg[u].size() == 1 && fa) {
		mx[u] = 1;
		return;
	}
	vi cr;
	for(auto v : eg[u]) {
		if(v == fa) continue;
		dfs(v, u);
		cr.pb(mx[v]);
	}
	sort(cr.begin(), cr.end());
	mx[u] = cr[cr.size() - 1] + 1;
	for(int i = 0; i < cr.size() - 1; i++) cur.pb(cr[i]);
}
int main()
{
	// freopen("test.in", "r", stdin);
	cin >> n >> k;
	for(int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		eg[u].pb(v), eg[v].pb(u);
	}
	// puts("ok1");
	dfs(1, 0);
	cur.pb(mx[1]);
	sort(cur.begin(), cur.end());
	reverse(cur.begin(), cur.end());
	if(k > cur.size()) {
		b = 0;
		r = min(k, n / 2);
		if(r < cur.size()) r = cur.size();
	}
	else {
		r = k;
		b = n;
		for(int i = 0; i < k; i++) b -= cur[i];
		if(b > n / 2) b = n / 2;
	}
	ll ans = 1ll * (n - r - b) * (r - b);
	cout << ans << '\n';
	return 0;
}