2024-11-06-solution-cf1917e

巨大简单题。看完样例就会做了吧。

首先考虑如果权值最大的边和权值次大的边的和大于 $d$ 那么一定无解。（原因是树是联通的所以直径一定至少是这个值。）

不妨设最大权值为 $w$，次大的为 $w'$。

所以我们不妨直接把他们挂在一个节点上。考虑如果我们钦定这个直径包括了边权最大的那条边的话，那么就相当于我们还有在这个节点上面挂一条长度为 $d-w$ 的链。只要能凑出来就一定行。原因：我们把除了这条链上的边全部也挂在这个节点上，那么首先有 $d-w \geq w'$ 所以我们一定是会取这条链和最大权值边作为我们的直径的。接着考虑权值最大的边不作为直径上的边。那么我们就必须要挂两条权值和大于 $w$ 的链。同理在这种情况下我们也会直接选择这两条链。所以我们直接对这两部跑动态规划解决就可以了。使用 bitset 以做到 $O({d^3\over \omega})$。

// Problem: Construct Tree
// URL: https://www.luogu.com.cn/problem/CF1917F
// Writer: WRuperD
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 2e3 + 10;

int a[MAX];
bool f[MAX];
bitset <MAX> f2[MAX];

void solve(){
	int n = read(), d = read();
	for(int i = 1; i <= n; i++){
		a[i] = read();
	}
	sort(a + 1, a + n + 1);
	if(a[n] + a[n - 1] > d){
		puts("NO");
		return ;
	}
	d -= a[n];
	for(int i = 0; i < MAX; i++)	f[i] = 0;
	for(int i = 0; i < MAX; i++)	for(int j = 0; j < MAX; j++)	f2[i][j] = 0;
	f[0] = 1;
	for(int i = 1; i < n; i++){
		for(int j = d; j >= a[i]; j--){
			f[j] |= f[j - a[i]];
		}
	}
	f2[0][0] = 1;
	for(int i = 1; i < n; i++){
		for(int j = d + a[n]; j >= 0; j--){
			bitset <MAX> ans = f2[j];
			if(j >= a[i])	ans |= f2[j - a[i]];
			ans |= f2[j] << a[i];
			f2[j] = ans;
		}
	}
	if(f[d]){
		puts("Yes");
	}else{
		for(int i = a[n]; i <= d; i++){
			int j = d + a[n] - i;
			if(j < a[n])	continue;
			if(f2[i][j]){
				puts("Yes");
				return ;
			}
		}
		puts("No");
	}
}

signed main(){
	int t = read();
	while(t--)	solve();
	return 0;
}