首先，吐槽一下这道题：
为啥去买东西还往回走的啊，为啥买水果还能往回走的啊，奇怪的买东西方式增加了
第一次看到这道题的时候，没理解题意，以为不能回头走，想着树剖秒了
但是样例说明，可以往后走 自闭
正片
之后思考了一下，发现题目实际是求这个东西：存不存在有 (x) 个连通的点，其中有 (y) 个水果店
把样例图建出来之后发现了一个奇怪的现象，即
在同一棵子树里选固定个商铺，其中水果店的个数在一个区间里
（我也不知道表达地是否准确，反正差不多理解就行）
然后感觉可以 (DP) 试一下
设 (fmax[u][i]) 表示 (u) 节点的子树中选取 (i) 个点（包括 (u) 节点） ， 的情况下最多的水果店数
设 (fmin[u][i]) 表示 (u) 节点的子树中选取 (i) 个点（包括 (u) 节点） ， 的情况下的最少水果店数
更新：
设 (size[u]) 为 (u) 的子树大小
对于 (1 leq k leq size[u]) 且 (1 leq j leq size[v])
这个地方有点类似于 (01) 背包（反正我是这么理解的）
需要注意的坑点是 (k) 从大到小枚举 ， (j) 从小到大枚举，因为不能覆盖之前的
得到 (fmax) 和 (fmin)之后，就意味着从 (fmax[u][k]) 至 (fmin[u][k]) 的区间是合法的
所以将 (fmax) 和 (fmin) 的值更新到 (dpmax) 和 (dpmin) 里就可以了
假设询问为 (x y)
(dpmax[x]) 表示 (y) 可能的最大值
(dpmin[x]) 表示 (y) 可能的最小值
询问的时候判断 (y) 是不是在 (dpmax[x]) 和 (dpmin[x]) 之间就可以了
然后另外的一些坑点：
- (size[u]) 要边 (dfs) 边更新，因为如果先预处理 (size[u]) 的话会更新时出错（自行思考）
2.要先把 (fmin) 和 (dpmin) 赋值无限大
然后就没啥好说的了吧。。
至于复杂度嘛，我也不知道，不过目测是 (O(n^3)) 的 （(dfs) * (for) * (for)）
完结撒花
代码：
#include<bits/stdc++.h>
namespace my_std
{
using namespace std;
#define int long long
#define R register
#define rep(i,a,b) for (R int i=(a);i<=(b);i++)
#define drep(i,a,b) for (R int i=(a);i>=(b);i--)
#define go(u) for (R int i=head[(u)];i;i=e[i].nxt)
#define pf printf
#define writeln(x) write(x),putchar('
')
#define writesp(x) write(x),putchar(' ')
#define mem(x,v) memset(x,v,sizeof(x))
typedef long long ll;
const int INF=0x7fffffff;
inline int read()
{
int sum=0,f=0;
char c=getchar();
while (!isdigit(c))
{
f|=(c=='-');
c=getchar();
}
while (isdigit(c))
{
sum=(sum<<1)+(sum<<3)+(c^48);
c=getchar();
}
return f?-sum:sum;
}
void write(int k)
{
if (k<0) putchar('-'),k=-k;
if (k>=10) write(k/10);
putchar(k%10+'0');
}
inline void chkmax(int &x,int y)
{
if (x<y) x=y;
}
inline void chkmin(int &x,int y)
{
if (x>y) x=y;
}
}
using namespace my_std;
const int N=410;
int n,q,cnt,head[N];
int f_max[N][N],f_min[N][N];
int dpmax[N],dpmin[N];
int fruit[N],size[N];
struct edge
{
int to,nxt;
}e[N<<1];
inline void add(int u,int v)
{
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
inline void dfs(int u,int fa)
{
size[u]=1;
f_max[u][1]=f_min[u][1]=(fruit[u])?1:0;
go(u)
{
int v=e[i].to;
if (v==fa) continue;
dfs(v,u);
drep(k,size[u],1) rep(j,1,size[v])
{
chkmax(f_max[u][k+j],f_max[u][k]+f_max[v][j]);
chkmin(f_min[u][k+j],f_min[u][k]+f_min[v][j]);
}
size[u]+=size[v];
}
}
signed main()
{
n=read(),q=read();
rep(i,1,n-1)
{
int u=read(),v=read();
add(u,v),add(v,u);
}
rep(i,1,n) fruit[i]=read();
mem(dpmin,0x3f);mem(f_min,0x3f);
dfs(1,0);
rep(u,1,n) rep(i,1,size[u])
{
chkmax(dpmax[i],f_max[u][i]);
chkmin(dpmin[i],f_min[u][i]);
}
rep(i,1,q)
{
int x=read(),y=read();
if (dpmin[x]<=y&&dpmax[x]>=y) pf ("Yes
");
else pf ("No
");
}
}
(NOIP 2020 rp++)