题目描述
很久很久之前,森林里住着一群兔子。有一天,兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由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
现在兔子们觉得樱花树上节点太多,希望去掉一些节点。当一个节点被去掉之后,这个节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。如果父节点也被删除,那么就会继续向上连接,直到第一个没有被删除的节点为止。
现在兔子们希望计算在不违背最大载重的情况下,最多能删除多少节点。
注意根节点不能被删除,被删除的节点不被计入载重。
输入
第一行输入两个正整数,n和m分别表示节点个数和最大载重
第二行n个整数c_i,表示第i个节点上的樱花个数
接下来n行,每行第一个数k_i表示这个节点的儿子个数,接下来k_i个整数表示这个节点儿子的编号
输出
一行一个整数,表示最多能删除多少节点。
样例输入
10 4
0 2 2 2 4 1 0 4 1 1
3 6 2 3
1 9
1 8
1 1
0
0
2 7 4
0
1 5
0
样例输出
4
提示
对于100%的数据,1 <= n <= 2000000, 1 <= m <= 100000, 0 <= c_i <= 1000
数据保证初始时,每个节点樱花数与儿子节点个数之和大于0且不超过m
题解
这道题就是前面三个题都没做透的罪魁祸首。。。考试的时候不应该觉得最后一题最好做,做了两个多小时也没做出什么名堂,反倒是前面那些看起来很不好把握的题更容易想。看到题目之后就开始死心眼地树归,局部用背包的思路。做的时候有两个问题:一是f数组太大根本没办法开,二是发现只要有一个点可以删去从此往上的几个值并不会有区别。调树归那些细微的地方花了很长时间,还不得不舍弃大测试点(后来证明几乎只有大测试点),状态转移方程确认了好几遍,做这道题实在是得不偿失。
事实证明它是个贪心。初始权值为son[x]+hh[x];每删去一个子节点,这个点的权值增加hh[子节点]+son[子节点]-1;子节点权值从小到大排序,加到m为止;子节点可以删去的下层节点直接转移到父亲身上。输入数据很多,要打快读。节点太多没法开数组存子节点,用邻接表的方法。
for(int i=h[x];i!=-1;i=fa[i].ne)
{
dfs(fa[i].z);
ge++;
zjd[ge].v=qz[fa[i].z];
zjd[ge].w=fa[i].z;
}
sort(zjd+1,zjd+ge+1,my_comp);
qz[x]=hh[x]+son[x];
for(int i=1;i<=ge;i++)
{
if(qz[x]+zjd[i].v-1<=m)
{
qz[x]+=zjd[i].v-1;
cf[x]++;
}
cf[x]+=cf[zjd[i].w];
}
不要以为一打dfs就是暴力枚举,dfs是生存技能,也是解题技能呢。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int sj=;
int n,m,hh[sj],son[sj],a,p,h[sj],e,cf[sj],qz[sj];
struct fz
{
int z,ne;
}fa[sj*];
inline int read()
{
int jg=,temp=;
temp=getchar()-'';
if(temp>=&&temp<=)
jg+=temp;
temp=getchar()-'';
while(temp!=-&&temp!=-)
{
if(temp>=&&temp<=)
{
jg*=;
jg+=temp;
}
temp=getchar()-'';
}
return jg;
}
void add(int x,int y)
{
fa[e].z=y;
fa[e].ne=h[x];
h[x]=e++;
}
void init()
{
n=read();
m=read();
memset(h,-,sizeof(h));
for(int i=;i<n;i++) hh[i]=read();
for(int i=;i<n;i++)
{
son[i]=read();
for(int j=;j<=son[i];j++)
{
a=read();
add(i,a);
}
}
}
struct ZJ
{
int v,w;
};
int my_comp(const ZJ&a,const ZJ&b)
{
if(a.v<b.v)
return ;
return ;
}
void dfs(int x)
{
int ge=;
ZJ zjd[];
for(int i=h[x];i!=-;i=fa[i].ne)
{
dfs(fa[i].z);
ge++;
zjd[ge].v=qz[fa[i].z];
zjd[ge].w=fa[i].z;
}
sort(zjd+,zjd+ge+,my_comp);
qz[x]=hh[x]+son[x];
for(int i=;i<=ge;i++)
{
if(qz[x]+zjd[i].v-<=m)
{
qz[x]+=zjd[i].v-;
cf[x]++;
}
cf[x]+=cf[zjd[i].w];
}
}
int main()
{
freopen("sakura.in","r",stdin);
freopen("sakura.out","w",stdout);
init();
dfs();
printf("%d",cf[]);
//while(1);
return ;
}