《关于 poaspoas 题解若干问题的解释》

仅代表个人观点，如有不对欢迎来喷

1. 题解多次提到“重心”，但是他似乎又和重心没有关系……

这其实是式子的问题。如果此时的根节点不是重心，那式子会变成这样：

$$\sum_{i\not=root}{|k-2 \times sz_i|}$$

注意到了吗？因为根是重心，所以每棵子树的大小都不会超过一半，我们才能直接使用 $k-2 \times sz_i$。否则肯定要计算绝对值。

2. 为什么重心错误时答案只会更小

考虑将重心移动一条边：因为重心的所有子树大小不会超过一半，所以最多有 $\frac{n}{2}$ 个点的深度 $-1$，至少有 $\frac{n}{2}$ 个点的深度 $+1$，答案不会更优。可以画棵树感受一下。

3. 关于为什么要用 bfs 染色，因为 bfs 按层遍历，所以越早染色的点深度越小（或者相等），符合贪心策略。并且这么做几乎可以保证根是重心（除非树的结构有限制）。

有一说一，poaspoas 题解读起来是真的感人

#include <bits/stdc++.h>
#define ll long long
#define mod (1000000007)
using namespace std;
const int N=5005;
int n,m,k,s,t,de[N],a[N],tot;
ll ans[N];
vector<int> e[N];
queue<pair<int,int>> q;
void bfs(int u){
	de[u]=0;tot=0;
	q.push({u,0});
	while (!q.empty()){
		int u=q.front().first;
		int fa=q.front().second;
		q.pop();
		a[++tot]=de[u];
		for (int &v:e[u]){
			if (v==fa) continue;
			de[v]=de[u]+1;
			q.push({v,u});
		}
	}
} 
int main(){
	cin>>n;
	for (int i=1;i<n;++i){
		cin>>s>>t;
		e[s].push_back(t);
		e[t].push_back(s);
	}
	for (int i=1;i<=n;++i){
		bfs(i);
		ll sum=0;
		for (int j=1;j<=n;++j){
			sum+=a[j];
			ans[j]=max(ans[j],(n-1)*j-2*sum);
		}
	}
	cout<<0;
	for (int i=1;i<=n;++i) cout<<' '<<ans[i];
}