题解：AT_abc416_f [ABC416F] Paint Tree 2

· · 题解

题目 link

注意到以 x 为根的子树情况一共有三种，x 和 x 子树有 2 个链一起被染，和子树中一条链一起被染，x 没有被染。我们假设 pos_{x, j, t} 表示 x 花费 j 次染色与子树中 t 条链一起被染的答案。为了方便表示，设 f_{x, j} 表示共和子树中 2 条链一起染花费 j，dp_{x, j} 表示和子树中一条且花费 j，g_{x, j} 表示 x 不染色花费 j。对于每一个儿子 to，有：

pos_{x, 1 \le j \le k + 1, t} = \max_{jj}\{pos_{x, j - jj, t} + \max(f_{to, jj}, g_{to, jj})\}

对于 t > 0，有：

pos_{x, 1 \le j \le k + 1, t \ge 1} = \max_{jj}\{pos_{x, j - jj, t - 1} + dp_{to, jj}\}

根据定义，显然有：

g_{x, j} = pos_{x, j, 0} \quad dp_{x, j} = pos_{x, j, 1} + a_x \quad f_{x, j} = \max(pos_{x, j, 1}, pos_{x, j + 1, 2}) + a_x

答案就是最大的 g 和 f。

code