BZOJ-5072: [Lydsy十月月赛]小A的树

Description

小A 成为了一个园艺家！他有一棵n 个节点的树（如果你不知道树是什么，请看Hint 部分）。他不小心打翻了墨水瓶，使得树的一些节点被染黑了。小A 发现这棵染黑了的树很漂亮，于是想从树中取出一个x 个点的联通子图，使得这些点中恰有y 个黑点，他想知道他的愿望能否实现。可是他太小，不会算，请你帮帮他。n<=5000

考虑对于一个大小为x的联通子图，改变一个所属节点，发现其中的黑点个数只能够+1，-1 ，+0 。所以说对于以一个节点s为最前节点大小为x的联通子图中，其含有的黑点个数是一段区间（由一个图慢慢爬到另一个图）。
那么我们就可以跑树上背包了。设L[x][i]表示以x为最浅节点的联通子图中黑点的最少个数，R[x][i]表示最多个数。转移L[fa[x]][j+k]=Min(L[fa[x][j]]+L[x][k])。R同理。对于每个x统计一下两边的边界就行了（含有黑点数量连续的原因同理）。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 5100 
int n,m,head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
inline int Min(int x,int y){return x<y?x:y;}
inline int Max(int x,int y){return x<y?y:x;}
int b[N],L[N][N],R[N][N],l[N],r[N],siz[N];
void dfs(int x,int pre)
{
    siz[x]=1; L[x][1]=R[x][1]=b[x];
    for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
    {
        dfs(to[i],x);
        for(int j=siz[x];j;--j)
            for(int k=siz[to[i]];k;--k)
            {
                L[x][j+k]=Min(L[x][j+k],L[x][j]+L[to[i]][k]);
                R[x][j+k]=Max(R[x][j+k],R[x][j]+R[to[i]][k]);
            }
        siz[x]+=siz[to[i]];
    }
}
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        memset(head,0,sizeof head); cnt=0;
        scanf("%d%d",&n,&m); int x,y;
        for(int i=1;i!=n;++i)
        {
            scanf("%d%d",&x,&y);
            add(x,y); add(y,x);
        }
        for(int i=1;i<=n;++i) scanf("%d",b+i);
        memset(L,0x3f,sizeof L); memset(R,0xc0,sizeof R);
        dfs(1,0); memset(l,0x3f,sizeof l); memset(r,0xc0,sizeof r);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=siz[i];++j)
                l[j]=Min(l[j],L[i][j]),r[j]=Max(r[j],R[i][j]);
        while(m--)
        {
            scanf("%d%d",&x,&y);
            if(y>=l[x]&&y<=r[x]) puts("YES");
            else puts("NO");
        }
        puts("");
    }
    return 0;
}