B20J_4027_[HEOI2015]兔子与樱花

B20J_4027_[HEOI2015]兔子与樱花_树形DP

题意：

很久很久之前，森林里住着一群兔子。有一天，兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由n个树枝分叉点组成，编号从0到n-1，这n个分叉点由n-1个树枝连接，我们可以把它看成一个有根树结构，其中0号节点是根节点。这个树的每个节点上都会有一些樱花，其中第i个节点有c_i朵樱花。樱花树的每一个节点都有最大的载重m，对于每一个节点i，它的儿子节点的个数和i节点上樱花个数之和不能超过m，即son(i) + c_i <= m，其中son(i)表示i的儿子的个数，如果i为叶子节点，则son(i) = 0

现在兔子们觉得樱花树上节点太多，希望去掉一些节点。当一个节点被去掉之后，这个节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。如果父节点也被删除，那么就会继续向上连接，直到第一个没有被删除的节点为止。

现在兔子们希望计算在不违背最大载重的情况下，最多能删除多少节点。

注意根节点不能被删除，被删除的节点不被计入载重。

分析：

我们仔细思考一下就会发现从下往上删不会使答案变差，并且删儿子不会对父亲的祖先产生影响。

对于每个结点，贪心的取儿子中贡献小的，并加入到自身的贡献

一个点的贡献 = 儿子的个数 + 这个点的权值

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 2000050

int head[N],to[N<<1],nxt[N<<1],cnt;

int n,m,c[N],son[N],a[N],tot,b[N],ans,nm[N];

inline void add(int u,int v){

    to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;

}

void read(int &x){

    int f=1;x=0;char s=getchar();

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

    while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}

    x*=f;

}

void dfs(int x,int y){

    if(son[x]==0)return ;

    for(int i=head[x];i;i=nxt[i]){

        if(to[i]!=y){

            dfs(to[i],x);

        }

    }

    int cnt=0;

    for(int i=head[x];i;i=nxt[i]){

        if(to[i]!=y){

            b[++cnt]=c[to[i]];

        }

    }

    sort(b+1,b+cnt+1);

    c[x]+=son[x];

    for(int i=1;i<=cnt;i++){

        if(b[i]+c[x]-1<=m){

            c[x]+=b[i]-1;ans++;

        }else break;

    }

}

int main(){

    read(n);read(m);

    for(int i=1;i<=n;i++){

        read(c[i]);

    }

    int x,y;

    for(int i=1;i<=n;i++){

        read(x);son[i]=x;

        while(x--){

            read(y);y++;

            add(i,y);add(y,i);

        }

    }

    dfs(1,0);

    printf("%d",ans);

}

巴特西

B20J_4027_[HEOI2015]兔子与樱花_树形DP

最新文章

热门文章