记录【CF1187E Tree Painting】

传送门。

$\texttt{Description}$

给定 $n$ 个节点的树，初始每个点为白色，进行 $n$ 次操作，每次选择一个与一个黑点隔一条边的白点，将它染黑，然后获得该白点被染色前所在的白色联通块大小的权值。一开始可以操作任何点。求最大权值。

$1\le n\le 2\times 10^5$。

$\texttt{Solution}$

非常好的一道换根 $\texttt{DP}$。

我们不妨先对一个子树进行思考，设 $g_i$ 表示以 $i$ 为根的子树中，选择了 $i$ 后的最大贡献。

显然可以得到 $g_i=siz_i+\sum_{j\in son_i}g_j$。

因为第一次选了 $i$ 后可以获得整个子树大小的权值，之后一步只能选择 $i$ 的儿子。

我们设 $f_i$ 表示以 $i$ 为根时，先选 $i$ 后整棵树的最大权值。

这就像是一个换根 $\texttt{DP}$ 的正确姿势了。

先来表示 $f_1$，显然 $f_1=g_1$。

然后考虑换根。

若 $v$ 是 $u$ 的一个儿子。考虑 $f_v$ 的转移：

$$f_v=n+(n-siz_v+\sum_{i\in son_u\land i\neq v}g_i)+(\sum_{i\in son_v}g_i)$$。

第一个 $n$，表示选择了 $v$ 这个点，获得了整棵树的价值。

考虑第二个括号，表示是在以 $u$ 为根的前提下把 $v$ 这个子树刨去所得到的价值。一开始都是白点，可以获得这个子树的大小，即整个树的大小减去 $v$ 子树的大小。

之后再把所有儿子的贡献加起来。

考虑第三个括号也很显然，就是计算 $v$ 子树的贡献。即 $v$ 的所有儿子的贡献之和。

这个柿子显然可以化简，别忘记一开始我们求的 $g_i$，第三个括号可以直接换成 $g_v-siz_v$。

然后发现 $\sum_{i\in son_u\land i\neq v}g_i)+g_v$ 是可以合并的，即为 $\sum_{i\in son_u}g_i$。

所以最终

$$f_v=n-2siz_v+(\sum_{i\in son_u}g_i+n)$$

但这个 $\sum$ 我们不想要，发现后面那个括号的东西其实就是以 $u$ 为根时的答案。即 $f_u$。

那么我们最终的 $\texttt{DP}$ 转移方程就跃然纸上了：

$$f_v=n-2siz_v+f_u$$。