很久很久之前,森林里住着一群兔子。有一天,兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由 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#include 2#include 3#include 4#include 5#include 6 using namespace std;
- 7 vector < int > edge[2000010];
- 8 int n,
- m,
- ans;
- 9 int w[2000010];
- 10 bool cmp(int aa, int bb) {
- 11
- return w[aa] < w[bb];
- 12
- }
- 13 void dfs(int u) {
- 14
- for (int i = 0; i) dfs(edge[u][i]);
- 15 sort(edge[u].begin(), edge[u].end(), cmp);
- 16 w[u] += edge[u].size();
- 17
- for (int i = 0; i) 18
- if (w[u] + w[edge[u][i]] - 1 <= m) {
- 19 w[u] += w[edge[u][i]] - 1;
- 20 ans++;
- 21
- }
- 22
- else break;
- 23
- }
- 24 int main() {
- 25 scanf("%d%d", &n, &m);
- 26
- for (int i = 0; i "%d", &w[i]);
- 27 int k,
- a;
- 28
- for (int i = 0; i) {
- 29 scanf("%d", &k);
- 30
- for (int j = 1; j <= k; j++) {
- 31 scanf("%d", &a);
- 32 edge[i].push_back(a);
- 33
- }
- 34
- }
- 35 dfs(0);
- 36 printf("%d", ans);
- 37
- return 0;
- 38
- }