【BZOJ5072】[Lydsy十月月赛]小A的树 树形DP

【BZOJ5072】[Lydsy十月月赛]小A的树

题解：考虑我们从一个联通块中替换掉一个点，导致黑点数量的变化最多为1。所以我们考虑维护对于所有的x，y的最大值和最小值是多少。如果询问的y在最大值和最小值之间，则一定是存在的。处理最大和最小值用树形背包即可。

#include <bits/stdc++.h>

using namespace std;

int n,m,cnt,T;

int f[5010][5010],g[5010][5010],v[5010],sg[5010],sf[5010],siz[5010],ff[5010],gg[5010];

int to[10010],next[10010],head[5010];

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

void dfs(int x,int fa)

{

	siz[x]=1;

	int i,j,k,y;

	f[x][1]=g[x][1]=v[x];

	for(i=head[x];i!=-1;i=next[i])	if(to[i]!=fa)

	{

		y=to[i],dfs(y,x);

		memcpy(ff,f[x],sizeof(f[x])),memcpy(gg,g[x],sizeof(g[x]));

		for(j=1;j<=siz[x];j++)	for(k=1;k<=siz[y];k++)

		{

			ff[j+k]=max(ff[j+k],f[x][j]+f[y][k]);

			gg[j+k]=min(gg[j+k],g[x][j]+g[y][k]);

		}

		siz[x]+=siz[y];

		for(j=1;j<=siz[x];j++)	f[x][j]=ff[j],g[x][j]=gg[j];

	}

	for(i=1;i<=siz[x];i++)	sf[i]=max(sf[i],f[x][i]),sg[i]=min(sg[i],g[x][i]);

}

inline void add(int a,int b)

{

	to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;

}

void work()

{

	int i,a,b;

	n=rd(),m=rd();

	memset(head,-1,sizeof(head)),cnt=0;

	memset(f,0xc0,sizeof(f)),memset(g,0x3f,sizeof(g)),memset(sf,0xc0,sizeof(sf)),memset(sg,0x3f,sizeof(sg));

	for(i=1;i<n;i++)	a=rd(),b=rd(),add(a,b),add(b,a);

	for(i=1;i<=n;i++)	v[i]=rd();

	dfs(1,0);

	for(i=1;i<=m;i++)

	{

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

		if(b<=sf[a]&&b>=sg[a])	printf("YES\n");

		else	printf("NO\n");

	}

	printf("\n");

}

int main()

{

	T=rd();

	while(T--)	work();

	return 0;

}//1 9 4 4 1 1 5 1 2 3 2 3 6 6 7 6 8 9 6 0 1 0 1 0 0 1 0 1 3 2 7 3 4 0 9 5