Codechef-BLACKCOM（树形背包dp）

题意：

给你一棵由 N 个节点构成的树 T。节点按照 1 到 N 编号，每个节点要么是白色，要么是黑色。有 Q 组询问，每组询问形如 (s, b)。你需要检查是否存在一个连通子图，其大小恰好是 s，并且包含恰好 b 个黑色节点。

输入第一行，包含一个整数 T，表示测试数据组数。对于每组测试数据：

第一行包含两个整数 N 和 Q，分别表示树的节点个数和询问个数。

接下来 N - 1 行，每行包含两个整数 ui 和 vi，表示在树中 ui 和 vi 之间存在一条边。

接下来一行包含 N 个整数，c1, c2, ... , cN。如果 ci 为 0 表示第 i 个节点是白色的，如果 ci 为

1 表示第 i 个节点是黑色的。

接下来 Q 行，每行包含两个整数 si 和 bi，表示一组形如 (si, bi) 的询问。

对于每组询问输出一行字符串表示答案，其中 Yes 表示存在一个符合要求的连

通子图，No 表示不存在。

1 <= T <= 5, 2 <= N <= 5e3, 1 <= Q <= 1e5, 1 <= ui, vi <= N。

0 <= ci <= 1, 0 <= bi <= N, 1 <= si <= N, bi <= si。

分析：

注意到对于一个确定的子树，如果固定取x个点，那么黑色节点的个数是一段连续的区间

所以dp[u][i] dp1[u][i]表示以u为根的子树取i个节点，最少包含dp[u][i]个黑点，最多包含dp1[u][i]个黑点

以dp[u][i]为例

dp[u][i+j]=min(dp[u][i+j],dp[u][i]+dp[v][j])

树形背包的时候注意循环要从大到小（不然会被覆盖）

时间复杂度O(n^2)（不会证复杂度是O(n^2)有待填坑……）

巴特西