首页 技术 正文
技术 2022年11月21日
0 收藏 352 点赞 3,866 浏览 638 个字

题意:

给你一棵由 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)有待填坑……)

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,020
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,513
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,359
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,142
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,772
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,850