[BZOJ] 5072: [Lydsy1710月赛]小A的树

(nleq 5000)，树上(O(n^2))的算法，大概就是树形背包了

对于一个联通块大小，能选出的黑点个数一定是连续的，这就是背包的依据

所以我们记录背包的上下界，即(f[x][j])和(g[x][j])分别表示以(x)为根的子树，选(j)大小的联通块，最多/最少的黑点数

假设考虑到了子树(v)，就有

[f[x][j+k]=max{f[x][j]+f[v][k]}\ g[x][j+k]=min{g[x][j]+g[v][k]} ]

也就是子树的合并，然后更新(size)信息即可

边界(f[x][1]=g[x][1]=color[x])

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

inline int rd(){
  int ret=0,f=1;char c;
  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
  while(isdigit(c))ret=ret*10+c-'0',c=getchar();
  return ret*f;
}
#define space() putchar(' ')
#define nextline() putchar('
')

const int MAXN = 5005;

inline void upmax(int &x,int y){x=max(x,y);}
inline void upmin(int &x,int y){x=min(x,y);}

int nex[MAXN<<1],to[MAXN<<1];
int head[MAXN],ecnt;
inline void add(int x,int y){
  nex[++ecnt]=head[x];
  to[ecnt]=y;
  head[x]=ecnt;
}

int f[MAXN][MAXN],g[MAXN][MAXN];
int color[MAXN];
int n,q;

int siz[MAXN],sum[MAXN];
void init(){
  memset(f,0xcf,sizeof(f));
  memset(g,0x3f,sizeof(g));
  memset(head,0,sizeof(head));
  memset(to,0,sizeof(to));
  memset(nex,0,sizeof(nex));
  memset(siz,0,sizeof(siz));
  ecnt=0;
}

void dfs(int x,int pre){
  siz[x]=1;
  f[x][1]=g[x][1]=color[x];
  for(int i=head[x];i;i=nex[i]){
    int v=to[i];
    if(v==pre)continue;
    dfs(v,x);
    for(int j=siz[x];j;j--){
      for(int k=siz[v];k;k--){
        upmax(f[x][j+k],f[x][j]+f[v][k]);
        upmin(g[x][j+k],g[x][j]+g[v][k]);
      }
    }
    siz[x]+=siz[v];
  }
  for(int i=1;i<=n;i++)upmax(f[0][i],f[x][i]),upmin(g[0][i],g[x][i]);
}
void solve(){
  n=rd();q=rd();
  int x,y;
  for(int i=1;i<n;i++){
    x=rd();y=rd();
    add(x,y);add(y,x);
  }
  for(int i=1;i<=n;i++)color[i]=rd();
  dfs(1,0);
  for(int i=1;i<=q;i++){
    x=rd();y=rd();
    if(g[0][x]<=y&&y<=f[0][x])puts("YES");
    else puts("NO");
  }
}

int main(){
  int T=rd();
  while(T--)init(),solve(),nextline();
  return 0;
}