已知花意，未见其花，已见其花，未闻花名，再见其花，落泪千溟，未闻花名，但识花香，已知花名，花已不在。未闻花名，但识花香，再遇花时，泪已千行。
——《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

数据范围和约定

对于$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;
}