「ZR 18 省选 3」题解
A. 树的染色如果确定了某个点的颜色，我们肯定是要求这个点子树内和这个点不同的点的权值和尽量小。我们设 $f_v$ 表示钦定 $v$ 是白色，子树内是黑色的点的权值和的最小值。合并子树的时候钦定当前的根是白色，如果儿子 $x$ 和根同色子树和贡献 $a_x$，答案贡献 $f_x$；否则子树和贡献 $f_x$，答案贡献 $a_x$，背包合并即可。复杂度 $O(nm)$。#include <...
A. 树的染色如果确定了某个点的颜色，我们肯定是要求这个点子树内和这个点不同的点的权值和尽量小。我们设 $f_v$ 表示钦定 $v$ 是白色，子树内是黑色的点的权值和的最小值。合并子树的时候钦定当前的根是白色，如果儿子 $x$ 和根同色子树和贡献 $a_x$，答案贡献 $f_x$；否则子树和贡献 $f_x$，答案贡献 $a_x$，背包合并即可。复杂度 $O(nm)$。#include <...