详细题解

1. 基本观察与预处理

将边长按非递减排序：
$l_1 \le l_2 \le \dots \le l_n$。
树有 $n+1$ 个节点，$n$ 条边，带权直径定义为树上最远两点之间的路径长度之和。

引理：任意一棵树中，直径至少为 $l_n + l_{n-1}$。
证明：取最长边 $e_n$（长度 $l_n$）和次长边 $e_{n-1}$（长度 $l_{n-1}$）。在树中，连接 $e_n$ 的某个端点和 $e_{n-1}$ 的某个端点的唯一路径一定包含这两条边（可能还经过其他边），因此路径长度 $\ge l_n + l_{n-1}$。故直径 $\ge l_n + l_{n-1}$。

因此，若 $l_n + l_{n-1} > d$，直接输出 No。

2. 分类构造

我们尝试用给定的 $n$ 条边构造一棵树，使其直径恰好为 $d$。
直径是一条简单路径，设其顶点序列为 $v_1, v_2, \dots, v_{k+1}$，边依次为 $e_1, e_2, \dots, e_k$，总长度 $\sum_{i=1}^k \text{len}(e_i) = d$。
其余 $n-k$ 条边需要挂在直径的某个顶点上（不能挂在边上，因为树中边只能连接节点）。

情况一：最长边 $l_n$ 属于直径

假设直径包含 $l_n$。
令直径上的边长集合为 $S$，满足 $l_n \in S$ 且 $\sum_{x \in S} x = d$。
构造方法：

• 将 $S$ 中的边按任意顺序连成一条路径（例如 $v_1 - v_2 - \dots - v_{|S|+1}$），使得路径总长为 $d$。
• 取路径上的某个内部顶点 $v$（例如 $v_2$），将剩余的所有边（长度均 $\le l_n$）全部接到 $v$ 上。

需要验证直径不会变大：
设 $v$ 到路径左端 $v_1$ 的距离为 $a$，到右端 $v_{|S|+1}$ 的距离为 $b$，则 $a+b = d$。
对于任意一条挂在 $v$ 上的边，长度为 $x \le l_n$，新叶子到 $v_1$ 的距离为 $a+x$，到 $v_{|S|+1}$ 的距离为 $b+x$。
由于 $l_n \le l_{n-1}$ 且 $l_n + l_{n-1} \le d$，可得 $l_n \le d - l_{n-1} \le d - l_n$（因为 $l_{n-1} \ge l_n$），所以 $l_n \le d - l_n$。
而 $a$ 和 $b$ 中至少有一个 $\le d/2$，另一个 $\ge d/2$，但为了安全我们只需将 $v$ 选为 $v_2$（即 $l_n$ 边的一个端点）。此时若 $l_n$ 是路径的第一条边，则 $a = l_n$，$b = d - l_n$。
因为 $x \le l_n$，有 $a+x \le l_n + l_n \le d$（由 $2l_n \le d$ 保证），且 $b+x \le (d-l_n) + l_n = d$。
因此所有新路径长度 $\le d$，直径仍为 $d$。

结论：若存在一个包含 $l_n$ 的子集，其和为 $d$，则答案为 Yes。
判断方法：对 $n$ 条边做 0/1 背包（$d \le 2000$），检查能否凑出 $d$ 且同时包含 $l_n$（等价于先用 $l_n$ 初始化背包，再对其它边做背包）。

情况二：最长边 $l_n$ 不属于直径

此时直径完全由其它 $n-1$ 条边中的若干条构成，总和为 $d$。
设直径上的顶点序列为 $v_1, v_2, \dots, v_{m+1}$，边集 $S \subseteq \{l_1,\dots,l_{n-1}\}$，$\sum_{x \in S} x = d$。
我们需要将 $l_n$ 以及所有不在 $S$ 中的边（包括 $l_n$）挂到直径上的某个顶点 $v'$ 上，且不能产生长度超过 $d$ 的路径。

设 $v'$ 将直径分为左右两段，长度分别为 $a$ 和 $b$（$a+b = d$）。
挂在 $v'$ 上的任一条边长度为 $x$，新叶子到 $v_1$ 的距离为 $a+x$，到 $v_{m+1}$ 的距离为 $b+x$。
要求 $a+x \le d$ 且 $b+x \le d$，即 $x \le \min(a, b)$。
由于最长边 $l_n$ 也要挂上去，最严格的条件是 $l_n \le \min(a, b)$，即

$$a \ge l_n,\quad b \ge l_n.$$

又因为 $a+b = d$，所以必须 $d \ge 2l_n$。

因此，问题转化为：是否存在一个子集 $S \subseteq \{l_1,\dots,l_{n-1}\}$ 满足：

• $\sum_{x \in S} x = d$；
• 可以将 $S$ 中的边排列成一条路径，并选定一个顶点 $v'$，使得该顶点到路径两端的距离 $a$ 和 $b$ 满足 $a \ge l_n$ 且 $b \ge l_n$。

由于 $S$ 中的边可以任意排序，顶点 $v'$ 可以对应路径上的任意一个顶点。设 $a$ 为从某一端到该顶点的距离，则 $a$ 必须是 $S$ 的某个子集和（即前缀和），$b = d - a$ 是补集和。
因此我们需要存在一个子集 $T \subseteq S$，使得 $\sum_{x \in T} x = a$ 且 $a \ge l_n$，$d-a \ge l_n$。

换句话说，我们需将 $\{l_1,\dots,l_{n-1}\}$ 中的某些边分配到左右两侧（分别代表直径上 $v'$ 左侧和右侧的边），剩余边（包括 $l_n$）不参与直径。设左侧和为 $a$，右侧和为 $b$，则 $a+b = d$，且 $a,b \ge l_n$。
此外，没有参与直径的边（包括 $l_n$）全部挂在 $v'$ 上，已经由 $a,b \ge l_n$ 保证了安全性。

因此，我们只需检查：能否从 $\{l_1,\dots,l_{n-1}\}$ 中选出一个子集，并将其划分为两个部分（左侧和右侧），使得两部分和分别为 $a$ 和 $b$，且 $a+b = d$，$a \ge l_n$，$b \ge l_n$。

3. 二维背包判定

定义 $dp[a][b] = \text{true}$ 表示可以用若干条边（来自 $\{l_1,\dots,l_{n-1}\}$）构造出左侧和为 $a$、右侧和为 $b$ 的两个不相交的边集（即每条边至多使用一次）。
初始 $dp[0][0] = \text{true}$。
对于每条长度 $l$，我们考虑三种选择：

• 不使用该边；
• 放在左侧，则 $a$ 增加 $l$；
• 放在右侧，则 $b$ 增加 $l$。

因为 $a$ 和 $b$ 都不超过 $d$，状态数为 $(d+1)^2$，$d \le 2000$，状态数约 $4 \times 10^6$。
使用二维 bitset 优化：
bitset<MAXD+1> dp[MAXD+1]，其中 dp[a] 是一个长度为 $d+1$ 的 bitset，表示在当前左侧和为 $a$ 时，右侧可能达到的和的集合。
转移时，对于每个 $l$，倒序更新 $a$（避免同一条边使用多次），并利用移位操作：
新 dp[a][b] = dp[a][b] | dp[a-l][b] | dp[a][b-l]。
用 bitset 实现时，dp[a] |= dp[a-l] 表示将右侧和集合并起来，但注意还要处理放在右侧的情况：
实际上可以用临时数组或从大到小更新，更简洁的方式是：

for (int i = d; i >= 0; --i) {
    dp[i] |= dp[i] << l;   // 将当前右侧集合整体左移 l，表示在右侧加 l
    if (i >= l) dp[i] |= dp[i-l]; // 左侧加 l
}

但需小心 dp[i] 的移位操作不应影响本层循环还未处理到的状态。通常采用二维 bitset 同时更新：

for (int i = d; i >= 0; --i) {
    for (int j = d; j >= 0; --j) {
        if (i >= l) dp[i][j] = dp[i][j] | dp[i-l][j];
        if (j >= l) dp[i][j] = dp[i][j] | dp[i][j-l];
    }
}

用 bitset 可以这样写：

for (int i = d; i >= l; --i) dp[i] |= dp[i-l];
for (int i = d; i >= 0; --i) dp[i] |= dp[i] << l;

注意顺序：先处理左侧加 $l$，再处理右侧加 $l$。因为右侧加 $l$ 会改变 dp[i] 自身的 bitset，所以需要用 dp[i] 的旧值来更新，应该倒序处理 i 且使用临时变量？实际上 dp[i] |= dp[i] << l 相当于在同一状态上扩展右侧，由于我们是倒序 i 且 dp[i] 本身是正在更新的，为了避免使用新产生的状态，通常的做法是先备份或按另一种顺序。更安全的方法是对每条边新建一个 ndp，但那样开销大。因为 $d=2000$，我们可以直接对每条边做三重循环（$a,b$ 均倒序），复杂度 $O(n \cdot d^2)$ 为 $2000 \times 4\times10^6 = 8\times10^9$，不可接受。因此必须用 bitset 且仔细安排顺序。

标准做法是：

bitset<MAXD+1> dp[MAXD+1];
dp[0][0] = 1;
for (int len : lengths_without_max) {
    for (int i = d; i >= 0; --i) {
        // 选择放在右侧：dp[i] 整体左移 len
        dp[i] |= (dp[i] << len);
        if (i >= len) {
            // 选择放在左侧：从 dp[i-len] 继承
            dp[i] |= dp[i - len];
        }
    }
}

这里先处理右侧移位，再处理左侧继承，且 i 从大到小。注意 dp[i] << len 可能会使某些位超出 $d$，需要掩码。
最终检查是否存在 $a$ 满足 $a \ge l_n$ 且 $d-a \ge l_n$，且 dp[a][d-a] == 1。

由于 $a$ 和 $b$ 对称，我们也可以只枚举 $a \le d/2$ 并检查 dp[a][d-a]，但需要同时检查 dp[d-a][a]。实际上 dp[a][b] 与 dp[b][a] 是等价的（因为我们没有区分左右顺序），所以只需检查 $a \le d/2$ 即可。

4. 算法流程

对于每个测试用例：

1. 读入 $n,d$ 和数组 $l$。
2. 对 $l$ 排序，令 $l_{\max} = l_n$，$l_{\text{second}} = l_{n-1}$。
3. 如果 $l_n + l_{n-1} > d$，输出 No，结束。
4. 检查情况一：用所有 $n$ 条边做背包，判断是否能凑出 $d$ 且必须包含 $l_n$。
   可以这样实现：初始化 bitset<MAXD+1> f; f[l_n] = 1; 然后对其它边做普通背包。最后若 f[d] == 1，输出 Yes。
5. 否则，检查情况二：
   • 如果 $d < 2 l_n$，输出 No（因为不可能同时满足 $a \ge l_n$ 且 $b \ge l_n$）。
   • 否则，对 $\{l_1,\dots,l_{n-1}\}$ 做上述二维背包，判断是否存在 $a \in [l_n, d-l_n]$ 使得 dp[a][d-a] == 1。若存在，输出 Yes，否则 No。

5. 复杂度分析

• 排序 $O(n \log n)$，总 $n$ 不超过 $2000$，可忽略。
• 背包部分：
  情况一：一维 bitset，$O(n \cdot d / 64)$，最大约 $2000 \times 2000 / 64 \approx 6.25\times 10^4$ 次位运算。
  情况二：二维 bitset，状态 $(d+1)$ 个 bitset，每个长度 $d+1$，总位数 $(d+1)^2 \approx 4\times10^6$。对于每条边，需要遍历 $i$ 从 $d$ 到 $0$ 并对 bitset 进行移位和或操作，每次移位复杂度 $O(d/64)$。总操作次数约为 $n \cdot d \cdot (d/64) = n \cdot d^2 / 64$。代入 $n \le 2000, d \le 2000$ 得 $2000 \times 4\times10^6 / 64 = 1.25\times 10^8$ 次位操作，现代计算机可以在 2 秒内完成（尤其是使用 std::bitset 优化）。
• 总测试用例 $t$ 之和满足 $n$ 总和不超 $2000$，因此最坏情况就是单个测试用例 $n=2000,d=2000$。

6. 示例验证

以第一个样例：
$n=4,d=10$, $l=[1,2,3,4]$。排序后 $[1,2,3,4]$，$l_n=4,l_{n-1}=3$，$4+3=7 \le 10$。
检查包含 4 的子集和为 10：$4+3+2+1=10$，存在，输出 Yes。

第二个样例：
$n=4,d=7$, $l=[1,4,3,4]$，排序 $[1,3,4,4]$，$l_n=4,l_{n-1}=4$，$4+4=8>7$，直接 No。

第三个样例：
$n=6,d=18$, $l=[2,4,3,7,6,7]$，排序 $[2,3,4,6,7,7]$，$l_n=7,l_{n-1}=7$，$7+7=14 \le 18$。
检查包含 7 的子集和为 18：尝试 $7+7+4=18$ 包含一个 7，存在，输出 Yes。

---

代码框架（C++）

#include <bits/stdc++.h>
using namespace std;
const int MAXD = 2000;

void solve() {
    int n, d;
    cin >> n >> d;
    vector<int> l(n);
    for (int i = 0; i < n; ++i) cin >> l[i];
    sort(l.begin(), l.end());
    int ln = l.back();
    int lprev = l[n-2];
    
    if (ln + lprev > d) {
        cout << "No\n";
        return;
    }
    
    // Case 1: diameter contains ln
    bitset<MAXD+1> f;
    f[ln] = 1;
    for (int i = 0; i < n-1; ++i) {
        f |= (f << l[i]);
    }
    if (f[d]) {
        cout << "Yes\n";
        return;
    }
    
    // Case 2: diameter does NOT contain ln
    if (d < 2 * ln) {
        cout << "No\n";
        return;
    }
    
    bitset<MAXD+1> dp[MAXD+1];
    bitset<MAXD+1> mask;
    for (int i = 0; i <= d; ++i) mask.set(i);
    dp[0][0] = 1;
    for (int i = 0; i < n-1; ++i) {
        int len = l[i];
        for (int a = d; a >= 0; --a) {
            // put on right side
            dp[a] |= (dp[a] << len) & mask;
            if (a >= len) {
                // put on left side
                dp[a] |= dp[a - len];
            }
        }
    }
    bool ok = false;
    for (int a = ln; a <= d - ln; ++a) {
        if (dp[a][d - a]) {
            ok = true;
            break;
        }
    }
    cout << (ok ? "Yes\n" : "No\n");
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}