#P11972. [2023年联测]如生存

    ID: 11122 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>贪心数据结构动态规划队列博弈论CF2200树形DP堆

[2023年联测]如生存

如生存(battle.cpp)

【题目描述】

nn 个房间和 n−1n-1 条长廊构成一棵树,是 Bob 闯关时遇到的特殊地形。初始 Bob 在 11 号房间,成功抵达 kk 号房间即闯关成功。

房间的门并没有上锁,也就是说房间之间都是可以相互抵达的。

每个房间内会有三种分布之一:空,食物,魔物。当 Bob 进入了空房间时,什么也不会发生;进入有食物的房间时可以恢复体力,各种食物可恢复的体力不一定相同;进入有魔物的房间时,需要消耗体力与其战斗,每次战斗所需体力不一定相同。

不幸的是,上一关的数据会继承到这一关,初始时 Bob 的体力为 00,当他的体力小于00 时就嗝屁了。

每个房间内的食物只可获取一次,魔物也只需战斗一次;之后可再次经过已处理的房间。

现在 Bob 想要知道自己有没有可能通过这一关,来决定上一关是否需要重开。

【输入格式】

第一行两个正整数n,kn , k,含义如题面所述;

第二行nn 个整数,第ii 个整数 aia_{i} 表示ii 号房间内的分布情况:ai=0a_{i}=0 为空;ai>0a_{i} > 0 为食物,可恢复 aia_{i} 点体力;ai<0a_{i} < 0 为魔物,战斗需−ai- a_{i} 点体力。

接下来n−1n-1 行,每行两个正整数u,vu , v 表示 uu 号房间和vv 号房间之间有一条长廊连接。

【输出格式】

如果 Bob 能通过此关,输出 Yes ,否则输出 No 。

【输入输出样例】

样例输入

7 7
0 -3 2 2 3 -4 0
1 2
2 3
2 4
1 5
5 6
6 7

样例输出

Yes

一种可行的路线:先去 55 号房间,体力增长为 33;然后去 22 号房间,体力降为 00;再去 33、44 号房间,体力增长为 44;再去 66 号房间,体力降为 00;最后去 77 号房间,闯关成功。两次前往不相邻房间时,沿树上的路径经过已处理的房间。

样例输入

3 2
0 3 -4
1 3
2 3

样例输出

No

【数据规模及约定】

对于 100%100\% 的测试数据,2≤n≤2×1052\le n\le2\times10^5,2≤k≤n2\le k\le n,a1=0a_1=0,∣ai∣≤106\lvert a_i\rvert\le10^6。原 PDF 的样例 2 把首项写成 33,与本段明确给出的 a1=0a_1=0 冲突。本版将该样例首项修正为 00,输出 No 不变;正式数据范围保持原约定。

Subtask nn 的上限 特殊性质 分值
1 5 无 10
2 20 20
3 10310^3 A 10
4 无 20
5 2×1052\times10^5 A 10
6 B
7 10510^5 无
8 2×1052\times10^5

特殊性质 A:图为一条链。特殊性质 B:所有边满足 u=1u=1。