Description：

给出一棵 $n$ 个点的树，每个点有黑白两种颜色。 $q$ 次询问，每次询问给出 $x$ 和 $y$ ，问能否选出一个 $x$ 个点的联通子图，使得其中黑点数目为 $y$ 。

$1\leqslant n\leqslant 5000$

Solution：

首先有一个结论，就是如果对于某一个大小的联通块内含有黑点的最小值为 $L$ ，最大值为 $R$ ，那么 $L$ 和 $R$ 之间的所有值都是可以取到的，原因就是你删掉一个点再加一个点黑点个数最多变化一，所以树形 $DP$ 求以 $k$ 为根的子树中大小为 $k$ 的联通块内黑点个数最大 $/$ 最小分别为多少，最后把所有答案整合 $O(1)$ 比较就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int testcases;

int n,q;

#define MAXN 5001

int f[MAXN][MAXN],g[MAXN][MAXN];

int c[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

#define R register

bool v[MAXN];

int siz[MAXN];

void dp(int k)

{

	v[k] = true;

	siz[k] = 1;

	f[k][1] = g[k][1] = c[k];

	for(R int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dp(e[i].to);

		for(R int j = siz[k];j >= 1;--j)

		{

			for(R int l = siz[e[i].to];l >= 1;--l)

			{

				f[k][j + l] = max(f[k][j + l],f[k][j] + f[e[i].to][l]);

				g[k][j + l] = min(g[k][j + l],g[k][j] + g[e[i].to][l]);

			}

		}

		siz[k] += siz[e[i].to];

	}

	for(R int i = 1;i <= n;++i)

	{

		f[0][i] = max(f[0][i],f[k][i]);

		g[0][i] = min(g[0][i],g[k][i]);

	}

	v[k] = false;

	return;

}

inline void work()

{

	n = rd();q = rd();

	R int a,b;

	memset(lin,0,sizeof(lin));

	edgenum = 0;

	for(R int i = 1;i < n;++i)

	{

		a = rd();b = rd();

		add(a,b);

	}

	for(R int i = 1;i <= n;++i)c[i] = rd();

	memset(f,0xc0,sizeof(f));

	memset(g,0x3f,sizeof(g));

	dp(1);

	for(R int i = 1;i <= q;++i)

	{

		a = rd();b = rd();

		puts((g[0][a] <= b && b <= f[0][a]) ? "YES" : "NO");

	}

	puts("");

	return;

}

int main()

{

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}