对于某一大小的连通子图包含的黑点的数目的最大值和最小值都能取到
考虑树形dp
$f[i][j]$ 表示从 $i$ 的子树中选出大小为 $j$ 的联通子图黑点数目的最小值
$g[i][j]$ 表示从 $i$ 的子树中选出大小为 $j$ 的联通子图黑点数目的最大值
树形dp转移

#include <bits/stdc++.h>

const int N = ;

#define gc getchar()

inline int read() {
int x = ; char c = gc;
while(c < '' || c > '') c = gc;
while(c >= '' && c <= '') x = x * + c - '', c = gc;
return x;
} int head[N], cnt;
struct Node {
int u, v, nxt;
} G[N << ];
int n, q;
int v[N];
int f[N][N], g[N][N];
int size[N]; inline void Add(int u, int v) {G[++ cnt].v = v; G[cnt].nxt = head[u]; head[u] = cnt;} void Dfs(int x, int fa) {
size[x] = , f[x][] = g[x][] = v[x];
for(int i = head[x]; ~ i; i = G[i].nxt) {
int v = G[i].v;
if(v != fa) {
Dfs(v, x);
for(int j = size[x]; j >= ; j --) {
for(int k = size[v]; k >= ; k --) {
f[x][j + k] = std:: min(f[x][j + k], f[x][j] + f[v][k]);
g[x][j + k] = std:: max(g[x][j + k], g[x][j] + g[v][k]);
}
}
size[x] += size[v];
}
}
for(int i = ; i <= n; i ++) {
f[][i] = std:: min(f[][i], f[x][i]);
g[][i] = std:: max(g[][i], g[x][i]);
}
} int main() {
int t = read();
for(; t; t --) {
cnt = ;
memset(f, 0x3f, sizeof f);
memset(g, 0xc0, sizeof g);
n = read(); q = read();
for(int i = ; i <= n; i ++) head[i] = -;
for(int i = ; i < n; i ++) {
int u = read(), v = read();
Add(u, v), Add(v, u);
}
for(int i = ; i <= n; i ++) v[i] = read();
Dfs(, );
for(; q; q --) {
int x = read(), y = read();
if(f[][x] <= y && y <= g[][x]) puts("YES");
else puts("NO");
}
puts("");
}
return ;
}

最新文章

  1. lucence.net+盘古分词
  2. Emmet 使用说明。
  3. io流操作大全
  4. BZOJ3941 : [Usaco2015 Feb]Fencing the Herd
  5. Spring项目启动时执行初始化方法
  6. NeHe OpenGL教程 第二十五课:变形
  7. Spring框架中的IOC和DI的区别
  8. CSS实现标题超出宽度省略号来表示
  9. python实现模拟登录【转】
  10. C#匿名类型(Anonymous Type)学习日记
  11. linux 调度器配制参数
  12. ios开发学习--歌词处理--解析lrc文件
  13. VAO VBO IBO大乱炖
  14. UVA - 10118 Free Candies 记忆化搜索经典
  15. postgresql 10 ssl 双向认证
  16. HDU 4570---Multi-bit Trie(区间DP)
  17. 自动化测试:java + testng + maven + reportng + jenkins + selenium (一)_基于win环境
  18. GRU门控制循环单元【转载】
  19. 全网最详细的hive-site.xml配置文件里添加&lt;name&gt;hive.cli.print.header&lt;/name&gt;和&lt;name&gt;hive.cli.print.current.db&lt;/name&gt;前后的变化(图文详解)
  20. scp命令:服务器间远程复制代码

热门文章

  1. c++学习---迭代器
  2. 2019杭电多校二 L. Longest Subarray (线段树)
  3. Crossword Expert CodeForces - 1194F (期望)
  4. ASM实例修改SYS密码
  5. List 集合 使用 remove 踩得坑
  6. 关于MySQL的驱动org.gjt.mm.mysql.Driver
  7. Intellij IDEA集成JProfiler性能分析神器
  8. keras 切换后端 TensorFlow,cntk,theano
  9. S2-016、S2-017
  10. sql语句开启事务