← 返回题目列表

Codeforces · 1917/F

F. 构造树

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

给定一个整数数组 $$$l_1、l_2、\dots、l_n$$$ 和一个整数 $$$d$$$。是否可以构建满足以下三个条件的树?

- 树包含 $$$n + 1$$$ 个节点。
- 第 $$$i$$$ 条边的长度等于 $$$l_i$$$。
- 树的(加权)直径等于 $$$d$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 250$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$, $$$d$$$ ($$$2 \leq n \leq 2000, 1 \leq d \leq 2000$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$l_1, l_2, \dots, l_n$$$ ($$$1 \leq l_i \leq d$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。

输出

对于每个测试用例,如果可以构建满足所有条件的树,则输出 $$$\texttt{Yes}$$$,否则输出 $$$\texttt{No}$$$。

您可以以任何大小写(大写或小写)打印字母。

示例

输入 #1

3
4 10
1 2 3 4
4 7
1 4 3 4
6 18
2 4 3 7 6 7

输出 #1

Yes
No
Yes

注意

下面为您提供了第一个和第三个测试用例的树的插图。其中一个直径通过将其边缘涂成红色来突出显示。