CF708C Centroids

容易想到点 i 是否可以经过改造成为重心，取决于将 i 最大的子树中最大的、小于 \frac{2}{n} 的子树 v 断开并连接到 i 上后，点 v 的子树的剩余部分大小能否小于 \frac{2}{n}。

换根dp。

先求出最大子树大小 maxsz[] 最大子树编号 maxId[] 子树中最大能断开的子树大小 dp[0][] 子树中次大能断开的子树大小 dp[1][]。

考虑换根时转移。

maxsz[v] = max(maxsz[v], maxsz[v])

最后修改：2021 年 03 月 13 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏