题目
题目链接：https://codeforces.com/contest/1842/problem/F
给定一棵 \(n\) 个点的树，你可以选择其中 \(k\) 个点染黑，定义一条边的价值为割去这条边之后，剩下两颗树的黑点数量差；一棵树的价值为所有边的价值之和。
对于 \(k\in [0,n]\)，求出树的价值的最大值。
\(n\leq 5000\)。
思路
不妨设点 \(rt\) 为根，设 \(cnt[i]\) 表示以 \(i\) 为根的子树内的黑点数量。那么如果染 \(k\) 个黑点，答案就是
\[\sum^{}_{i\neq rt}\left |(k-cnt[i])-cnt[i]\right |=\sum^{}_{i\neq rt}\left |k-2\times cnt[i]\right | \]这个绝对值很讨厌，但可以发现，如果点 \(rt\) 是所有黑点的重心的话，那么对于所有的 \(cnt[i]\ (i\neq rt)\)，都一定满足 \(2\times cnt[i]\leq k\)，此时答案就是
\[(n-1)\times k - 2\times \sum_{i\neq rt}cnt[i] \]我们发现如果选择点 \(x\) 染黑，那么从 \(x\) 的父亲到 \(rt\) 上所有点的 \(cnt\) 都要加一。那么为了最大化答案，我们只需要选择深度最小的 \(k\) 个节点染黑即可。
只需要枚举每一个点作为 \(rt\)，然后 BFS 计算所有 \(k\) 的答案即可。即使目前枚举的点不是重心也没关系，因为这样就会导致有些 \(k-2\times cnt<0\)，不会比最优答案大。
时间复杂度 \(O(n^2)\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=5010;
int n,dep[N],ans[N];
vector<int> e[N];
queue<int> q;
int main()
{
scanf("%d",&n);
for (int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
e[x].push_back(y); e[y].push_back(x);
}
printf("0 %d",n-1);
memset(ans,0x3f3f3f3f,sizeof(ans));
for (int i=1;i<=n;i++)
{
memset(dep,-1,sizeof(dep));
q.push(i); dep[i]=0;
int res=0,cnt=1;
while (q.size())
{
int u=q.front(); q.pop();
for (auto v:e[u])
if (dep[v]==-1)
{
dep[v]=dep[u]+1; res+=dep[v];
cnt++; ans[cnt]=min(ans[cnt],res);
q.push(v);
}
}
}
for (int i=2;i<=n;i++)
printf(" %d",(n-1)*i-2*ans[i]);
return 0;
}