CF1917F

大常熟另类做法。不用排序。

要求直径长度，则想到把直径这一条链拎出来处理。然后考虑其他边会接在哪里，发现树最优情况下一定是一个毛毛虫的形式。更进一步，所有边都挂在接近直径中点的点上。

然后再考虑这些不在直径中的，长度为 $l$ 的边带来的限制，设直径为 $d$，从每个点将直径切成两半，记其中一段为 $c_i$，则有 $\max(\min(c_i,d-c_i))\ge l$。

于是考虑一个 dp：设 $dp_{i,j,k}$ 表示只考虑前 $i$ 条边，当前已经选进直径的边长度之和为 $j$，不在直径中的 $l$ 的最大值为 $k$，是否可行。每次新加入一条边，长度为 $l_i$，就看它是否加入直径。转移即为：

$dp_{i,j,l_i}:=dp_{i,j,l_i}+\sum dp_{i-1,j,p\le l_i}$

$dp_{i,j,k>l_i}:=dp_{i,j,k}+dp_{i-1,j,k}$

$dp_{i,j,k}:=dp_{i,j,k}+dp_{i-1,j-l_i,k}$

在 bool 值下运算。

如果有 $dp_{n,i,j}$ 满足 $dp_{n,i,j}=1\land j\le\min(i,d-i)$ 则可行。

发现有一点小问题：有可能一个 $i$ 是无法满足最后获得长为 $d$ 的直径的。则再设一个 dp：$f_{i,j,k}$ 表示只考虑前 $i$ 条边，直径总长为 $j$，其中一段长为 $k$ 是否可行。也是 bool 背包转移。

然后发现上面两个东西都可以用 bitset 维护，然后就可以 $O(\dfrac{nd^2}{\omega})$ 做完了。

但是常数大，如果你在代码里多用左移/右移好像会 TLE，尽量少用，卡卡就过了。cf 机子真是令人流汗。

code：

int n,m;
bitset<N> dp[2][N],f[2][N];
void Yorushika(){
	scanf("%d%d",&n,&m);
	rep(i,0,m)dp[0][i].reset();
	rep(i,0,m)f[0][i].reset();
	dp[0][0].set(0),f[0][0].set(0);
	bitset<N> ALL;ALL.set();
	rep(i,1,n){
		int x,p=i&1;scanf("%d",&x);
		rep(j,0,m)dp[p][j].reset();
		rep(j,0,m)f[p][j].reset();
		bitset<N> S;
		rep(j,0,x)S.set(j);
		rep(j,0,m){
			dp[p][j][x]=(dp[p^1][j]&S).any();
			dp[p][j]|=dp[p^1][j]&(ALL^S);
		}
		rep(j,x,m)dp[p][j]|=dp[p^1][j-x];
		rep(j,x,m){
			f[p][j]|=f[p^1][j-x];
			f[p][j]|=f[p^1][j-x]<<x;
		}
		rep(j,0,m)f[p][j]|=f[p^1][j];
	}
	bool ans=0;
	rep(i,0,m)rep(j,0,m)ans|=f[n&1][m][i]&&dp[n&1][i][j]&&j<=min(i,m-i);
	puts(ans?"Yes":"No");
}
signed main(){
	int t=1;
		scanf("%d",&t);
	while(t--)
		Yorushika();
}