Problem Statement
小A 成为了一个园艺家！他有一棵n 个节点的树（如果你不知道树是什么，请看Hint 部分）。他不小心打翻了墨水瓶，使得树的一些节点被染黑了。小A 发现这棵染黑了的树很漂亮，于是想从树中取出一个x 个点的联通子图，使得这些点中恰有y 个黑点，他想知道他的愿望能否实现。可是他太小，不会算，请你帮帮他。
解题报告
这道题可以理解为：有n个点，每个点有其点权，一些点的点权是1，一些点的点权是0，选择每一个点都有代价，代价为1，问能否用大小为x的背包装下权值为y的点。
关于树上背包，有这么一篇博客，这里我们不仅算出最多能选的价值，也算出最小能选到的价值就好了。
具体的状态：
dp[u][j+k]//以u为根节点，一个子树选k个点，其他子树选u个点的最小价值
g[u][j+k]//以u为根节点，一个子树选k个点，其他子树选u个点的最大价值
转移：
dp[u][j+k]=min(dp[u][j+k],dp[u][j]+dp[v][k]),g[u][j+k]=max(g[u][j+k],g[u][j]+g[v][k]);
dp数组初值赋+inf，g数组赋0，搜索到每一个点的时候更改dp[u][1]/dp[v][1]。
代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
struct edge
{
int v,next;
}ed[*N+];
int T,n,q;
int w[N+],size[N+];
int dp[N+][N+],g[N+][N+];
int vmax[N+],vmin[N+];
int head[N+],num;
void build(int u,int v)
{
ed[++num].v=v;
ed[num].next=head[u];
head[u]=num;
}
void dfs(int u,int f)
{
size[u]=;
dp[u][]=w[u],g[u][]=w[u];
for(int i=head[u];i!=-;i=ed[i].next)
{
int v=ed[i].v;
if(v==f)continue;
dfs(v,u);
for(int j=size[u];j;j--)
for(int k=;k<=size[v];k++)
dp[u][j+k]=min(dp[u][j+k],dp[u][j]+dp[v][k]),
g[u][j+k]=max(g[u][j+k],g[u][j]+g[v][k]);
size[u]+=size[v];
}
for(int i=;i<=n;i++)vmin[i]=min(vmin[i],dp[u][i]),vmax[i]=max(vmax[i],g[u][i]);
}
void init()
{
memset(head,-,sizeof(head));num=;
memset(dp,,sizeof(dp));
memset(vmin,,sizeof(vmin));
memset(vmax,,sizeof(vmax));
memset(g,,sizeof(g));
}
int main()
{
for(scanf("%d",&T);T;T--)
{
init();
scanf("%d%d",&n,&q);
for(int i=;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
build(u,v);
build(v,u);
}
for(int i=;i<=n;i++)scanf("%d",&w[i]);
dfs(,);
for(int i=;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(y>=vmin[x]&&y<=vmax[x])printf("YES\n");
else printf("NO\n");
}
printf("\n");
}
return ;
}