Sweet Sugar

题目链接： Sweet Sugar 。

题目描述：

一颗 $n$ 个点的树，每个点有点权 $a_i$ ，求将树划分为若干个连通子图后点权和为 $k$ 的子图的个数的最大值。

$a_i\in\{0,1,2\},n,k\le 10^6$ 。

$60$ 分是显然的树形 DP 。

考虑最终的最优解的结构是什么。我们发现，当一个子树可以凑成长度为 $k$ 的子图时，我们必然应该把它划分为一个连通子图。这是它为上级贡献是没有意义的。

所以我们可以得出如下伪代码：

DFS(x):
something <- 0
for u in son[x]:
  DFS(u)
  ADD(x,u)
if(Can_Get_K(x))
  ans++
  DELETE(x)

重点就在如何判断一个子树是否能拼成一个 $k$ 的连通子图。

由于点权只有 $0,1,2$ ，所以考虑奇偶性相关。经过观察，我们发现如下性质：

• 如果一个子树满足它内部所有子树都不能拼出 $k$ ，且其可以拼出 $\ge k$ 的连通子图并且这个联通子图的权值和 $s$ 满足 $s \equiv k\pmod 2$ ，则这个子图可以拼出 $k$ 的连通子图。

证明：

删掉叶子 $0$ 没有意义。删掉叶子 $2$ 可以在不改变奇偶性的情况下进行减法。删掉叶子 $1$ 有一点复杂：

• 如果有 $2$ 个 $1$ 叶子，则也可以实现和 $2$ 一样的效果。
• 如果只有 $1$ 个 $1$ 叶子，此时考虑去掉所有其他的 $0,2$ 叶子的情况下子树仍然不能恰好为 $k$ 。此时形态必然为链。那么这种情况下就不满足 一个子树满足它内部所有子树都不能拼出 k 的限制了，这一点可以通过调整法证明。

于是我们就证明了了。

由此，定义 $f_{i,j}$ 表示子树 $i$ ，能拼出奇偶性为 $j$ 的最大值。转移十分显然。最终 Can_Get_K(x) 只需要判断 f[i][k&1]>=k 是否成立即可。

代码十分简单，不放了。