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

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

结论：.对于某一大小的连通子图，其包含黑点数的最小值与最大值之间的所有点数目都能够取得到。

简单证明一下：考虑一个连通子图删除一个点再加入一个点后，黑点的数目变化最多只为1。因此可以变化到[min,max]之间所有的数目。

然后就可以使用树形背包dp。设g[i][j]表示黑点数目的最大值。然后树形背包转移即可。

注意树形背包的正确枚举姿势：只使用已经遍历过的点数目和当前子树中的点数目转移，否则会被链卡到O(n3)。

时间复杂度)

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 5010
using namespace std;
int n,m,head[maxn],num,v[maxn],sz[maxn],f[maxn][maxn],g[maxn][maxn];
struct node{int to,pre;}e[maxn*2];
void Insert(int from,int to){
    e[++num].to=to;
    e[num].pre=head[from];
    head[from]=num;
}
void dfs(int x,int father){
    sz[x]=1;f[x][1]=g[x][1]=v[x];
    for(int i=head[x];i;i=e[i].pre){
        int to=e[i].to;
        if(to==father)continue;
        dfs(to,x);
        
        for(int j=sz[x];j>=1;j--)
            for(int k=sz[to];k>=1;k--){
                f[x][j+k]=min(f[x][j+k],f[x][j]+f[to][k]);
                g[x][j+k]=max(g[x][j+k],g[x][j]+g[to][k]);
            }
        sz[x]+=sz[to];
    }
    for(int i=1;i<=n;i++){
        f[0][i]=min(f[0][i],f[x][i]);
        g[0][i]=max(g[0][i],g[x][i]);
    }
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        memset(head,0,sizeof(head));num=0;
        memset(f,0x3f,sizeof(f));memset(g,0xc0,sizeof(g));
        scanf("%d%d",&n,&m);
        int x,y;
        for(int i=1;i<n;i++){
            scanf("%d%d",&x,&y);
            Insert(x,y);Insert(y,x);
        }
        for(int i=1;i<=n;i++)scanf("%d",&v[i]);
        dfs(1,0);
        while(m--){
            scanf("%d%d",&x,&y);
            if(y>=f[0][x]&&y<=g[0][x])puts("YES");
            else puts("NO");
        }
        puts("");
    }
    return 0;
}

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

相关推荐