已知花意,未见其花,已见其花,未闻花名,再见其花,落泪千溟,未闻花名,但识花香,已知花名,花已不在。未闻花名,但识花香,再遇花时,泪已千行。
——《secret base》

题意描述

很久很久之前,森林里住着一群兔子,有一天,兔子们突然决定要去看樱花。

兔子们所在森林里的樱花树由$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$个整数表示这个节点的子节点的编号


输出格式

输出仅有一行,包含一个整数$ans$,表示最多能删除多少节点。


Input & Output ‘s examples

Input ‘s eg

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

Output ‘s eg

4

数据范围和约定

对于$30\%$的数据,$1 < n < 5 \times 10^3, 1 < m < 100, 0 < c_i < 100$

对于$70\%$的数据,$1 < n < 2 \times 10^5, 1 < m < 2000, 0 < c_i < 1000$

对于$100\%$的数据,$1 < n < 2 \times 10^6, 1 < m < 100000, 0 < c_i < 1000$

数据保证初始时,每个节点樱花数与儿子节点个数之和小于$m$

约定根节点不可以被删除,被删除的节点不计入总权重。


分析

一道贪心好题。

首先,对于除根节点外的每个节点$i$,我们删除它所需要的代价是$son_i + c_i$(即其儿子的数量加上其樱花数),这些代价会直接转移到它的父节点上。

而父节点的承受能力是有限的。每一次删除后,父节点的代价都会加上其被删去的子节点的代价,这个代价越接近与给出的上限$m$,我们就越难进行下一步操作。

因此我们要尽量让删去节点$i$后,其父节点的代价尽量的小。

综上,我们可得贪心方案:在删除时,每一个节点都删去自己的子节点中代价最少的那一个,然后更新自己的代价,直到不能删除为止。


Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 2000001

using namespace std;

int n , m , opt , ans;

struct Edge{
int to;
int last;
}edge[N];

int head[N];
int edge_num;

I void add_edge(int from , int to){
edge[++ edge_num] = Edge{to , head[from]};
head[from] = edge_num;
}

int flower[N];
int son[N];
pair<int , int > node[N];

void search(int k){
int num = 0;
for(int i = head[k]; i; i = edge[i].last){
int to = edge[i].to;
search(to);
}
for(int i = head[k]; i ; i = edge[i].last){
int to = edge[i].to;
node[num ++] = make_pair(flower[to] + son[to] , to);
}
sort(node , node + num);
for(int i = 0; i < num; i ++){
int cut = node[i].second;
if(flower[cut] + flower[k] + son[cut] + son[k] - 1 <= m){
flower[k] += flower[cut];
son[k] += son[cut] - 1;
ans ++;
}
else{
break;
}
}
}

int main(){
scanf("%d %d" , &n , &m);
for(int i = 1; i <= n; i ++){
scanf("%d" , &flower[i]);
}
for(int i = 1; i <= n; i ++){
scanf("%d" , &son[i]);
for(int j = 1; j <= son[i]; j ++){
scanf("%d" , &opt);
add_edge(i , opt + 1);
}
}
search(1);
printf("%d" , ans);
return 0;
}

THE END