标签 Tree 下的文章

P1364 医院设置 — 换根DP

题面 https://www.luogu.com.cn/problem/P1364 题解 复杂度 $O(n)$ 高赞题解中说带权树的重心。其实关系不是最大，我们直接嗯推方程其实就可以了。 首先定义: $sz[u]$ 是以 $u$ 为根的子树大小 $f[u]$ 是将 $u$ 设置为医院时的总距离 我们不妨以 $1$ 为根。 第一遍 dfs 初始化 $sz$ 与 $f[1]$: 代码 #...