外贸公司的网站怎么做,百度高级搜索首页,开源镜像网站开发,网页设计与网站建设 作业题目描述 很久很久之前#xff0c;森林里住着一群兔子。有一天#xff0c;兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由n个树枝分叉点组成#xff0c;编号从0到n-1#xff0c;这n个分叉点由n-1个树枝连接#xff0c;我们可以把它看成一个有根树结…题目描述 很久很久之前森林里住着一群兔子。有一天兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由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个整数表示这个节点儿子的编号 输出格式 一行一个整数表示最多能删除多少节点。 输入输出样例 输入样例#1 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 输出样例#1 4 说明 对于30%的数据1 n 5000, 1 m 100, 0 c_i 100 对于70%的数据1 n 200000, 1 m 2000, 0 c_i 1000 对于100%的数据1 n 2000000, 1 m 100000, 0 c_i 1000 数据保证初始时每个节点樱花数与儿子节点个数之和大于0且不超过m HEOI2015 T1。 一上来的题应该不能太难吧所以我直接往贪心上想了2333幸好的确是个贪心题。 我们考虑一个点删除带来的影响(我们设一个节点的重量参数 h[i] son[i] c[i]) 一个点x被删除仅会影响父节点的重量参数且会让它的重量参数 c[x]son[x]-1也就是x的重量参数-1。 所以我们可以先预处理出所有点的重量参数因为上限都是m所以就可以直接从下向上贪心了。 #includebits/stdc.h
#define ll long long
#define maxn 2000005
using namespace std;
int to[maxn],ne[maxn];
int hd[maxn],n,m,c[maxn];
int siz[maxn],num0,ans;inline int read(){int x0; char chgetchar();while(!isdigit(ch)) chgetchar();for(;isdigit(ch);chgetchar()) xx*10ch-0;return x;
}void dfs(int x){ int T0,a[siz[x]3];siz[x]c[x];for(int ihd[x];i;ine[i]){dfs(to[i]),a[T]siz[to[i]];}sort(a1,aT1);for(int i1;iT;i){if(siz[x]a[i]-1m){siz[x]a[i]-1,ans;}else return;}
}int main(){scanf(%d%d,n,m);for(int i0;in;i) c[i]read();int K,SON;for(int i0;in;i){siz[i]Kread();while(K--){SONread();to[num]SON,ne[num]hd[i],hd[i]num;}}dfs(0);printf(%d\n,ans);return 0;
}转载于:https://www.cnblogs.com/JYYHH/p/8550444.html
