事实上自己方向一直是错的……
绝对值不好弄，我一开始的想法是直接去绝对值，但是不可避免地要 \(O(n^3)\)。
考虑我们直接钦定黑点重心为根，设这个根为 \(r\)，设 \(sz_i\) 为 \(i\) 子树内黑点数，由重心的性质，可以直接去绝对值，也就是说答案为 \(\sum\limits_{i \ne r} k - 2 sz_i\)。
考虑拆贡献，一个黑点 \(u\) 会对它的所有除了根的祖先都造成 \(-2\) 的贡献，也就是说贡献是 \(-2 \times \text{dis}(u, r)\)。于是我们贪心地选择与 \(r\) 的距离最小的染黑即可。
因为如果 \(r\) 不是重心，会产生负贡献，所以最优解一定是合法的。
时间复杂度 \(O(n^2)\)。
code
// Problem: F. Tenzing and Tree
// Contest: Codeforces - CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!)
// URL: https://codeforces.com/contest/1842/problem/F
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 5050;
int n, f[maxn], d[maxn];
vector<int> G[maxn];
void solve() {
scanf("%d", &n);
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
G[u].pb(v);
G[v].pb(u);
}
mems(f, 0x3f);
for (int u = 1; u <= n; ++u) {
queue<int> q;
for (int i = 1; i <= n; ++i) {
d[i] = -1;
}
q.push(u);
d[u] = 0;
int s = 0;
for (int i = 1; i <= n; ++i) {
int v = q.front();
q.pop();
s += d[v] * 2;
f[i] = min(f[i], s);
for (int w : G[v]) {
if (d[w] == -1) {
d[w] = d[v] + 1;
q.push(w);
}
}
}
}
printf("0 ");
for (int i = 1; i <= n; ++i) {
printf("%d ", i * (n - 1) - f[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}