CF1187E Tree Painting 题解
题意：树上 01 染色，一个点染上色获得的分数等于这个点原本所在的连通块的大小。
考虑树形 dp，则 dp_{fa} = size_{fa} + \sum_{u \in child_{fa}} dp_u
，其中 size_{fa} 表示以 fa 为根的子树的大小。
注意到总答案和根的选择有关系，朴素做法是直接运行 n 次树形 dp，复杂度为 $O(n^2)$，无法通过。
考虑使用换根 dp，考虑确定以 fa 为根时的答案，如何转移到以 u (u \in child_{fa}) 为根的答案。
\begin{aligned}
\because ans_{root} =& size_{root} + \sum_{u \in child_{root}} dp_u \\
\therefore ans_{u} =& (f_u - size_u) + (ans_{root} - f_u - size_u) + n \\
&(u\text{的孩子的贡献}) (root\text{其他孩子的贡献}) \\
=& ans_u - 2\times size_u + n
\end{aligned}
因此，只需要以 1 为根节点计算一次，随后进行答案转移即可。
CF1187E.cpp