← 返回题目列表

Codeforces · 2014/F

F. 警长的辩护

中文机器翻译题面 查看原题

民间英雄罗宾汉一直困扰着诺丁汉警长。警长知道罗宾汉即将袭击他的营地,他希望做好准备。

诺丁汉警长在建造营地时考虑到了战略,因此总共有 $$$n$$$ 营地,编号从 $$$1$$$ 到 $$$n$$$ 以及 $$$n-1$$$ 小径,每条小径连接两个营地。任何营地都可以从任何其他营地到达。每个营地最初有 $$$i$$$ 黄金 $$$a_i$$$。

按照现在的情况,所有的营地都会被罗宾摧毁。治安官可以通过从每个邻近营地中精确减去 $$$c$$$ 黄金来加强营地,并用它来为该营地建立更好的防御。强化营地并不会改变其黄金,只会改变其邻居的黄金。一个阵营可以拥有负金币。

罗宾汉发起攻击后,所有已加固的营地都在攻击中幸存下来,其他营地均被摧毁。

在罗宾汉袭击后,如果警长以最佳方式强化营地,他可以在幸存的营地中保留的最大黄金是多少?

营地 $$$a$$$ 是邻近的营地 $$$b$$$ 当且仅当存在连接 $$$a$$$ 和 $$$b$$$ 的路径。只有经过强化的营地才算得上答案,因为其他营地都被摧毁了。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例都以两个整数 $$$n$$$、$$$c$$$ ($$$1 \le n \le 2\cdot10^5, 1 \le c \le 10^9$$$) 开头——营地的数量以及从每个相邻营地获取的用于强化的黄金。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\dots,a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 每个阵营的初始黄金。

然后跟随 $$$n-1$$$ 行,每行都有整数 $$$u$$$、$$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — 意味着 $$$u$$$ 和 $$$v$$$ 之间有一条踪迹。

所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。

保证任何营地都可以从任何其他营地到达。

输出

输出一个整数,诺丁汉警长在罗宾汉袭击后幸存的营地中可以保留的最大黄金。

示例

输入 #1

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

输出 #1

3
8
0
17
26

注意

在第一个测试用例中,加强第二个基地是最佳的。每个基地的最终黄金是$$$[1,3,0]$$$。

在第二个测试用例中,强化所有基地是最佳的。每个基地的最终黄金是$$$[2,4,2]$$$。

在第三个测试用例中,最好不强化任何基础。