[HEOI2015]兔子与樱花

Description

很久很久之前，森林里住着一群兔子。有一天，兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由\(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\)

现在兔子们觉得樱花树上节点太多，希望去掉一些节点。当一个节点被去掉之后，这个节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。如果父节点也被删除，那么就会继续向上连接，直到第一个没有被删除的节点为止。

现在兔子们希望计算在不违背最大载重的情况下，最多能删除多少节点。

注意根节点不能被删除，被删除的节点不被计入载重。

Input

第一行输入两个正整数，\(n\)和\(m\)分别表示节点个数和最大载重

第二行\(n\)个整数\(c_i\)，表示第\(i\)个节点上的樱花个数

接下来\(n\)行，每行第一个数\(k_i\)表示这个节点的儿子个数，接下来\(k_i\)个整数表示这个节点儿子的编号

Output

一行一个整数，表示最多能删除多少节点。

Sample Input

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

Sample Output

HINT

对于100%的数据，\(1 <= n <= 2000000, 1 <= m <= 100000, 0 <= c_i <= 1000\)

数据保证初始时，每个节点樱花数与儿子节点个数之和大于\(0\)且不超过\(m\)

瞎懵的贪心，居然是正解思路？！惊了。奈何代码打崩了

贪心证明

转自YoungNeal

自底向上：从根节点 \(dfs\) ，从叶子结点向上回溯。路上如果遇到能删除的点就删，不必考虑其祖先。

证明：设点 \(i\) 的儿子是 \(j\) ，\(j\) 的兄弟是 \(p\) ，\(j\) 还有一个儿子是 \(q\)。

\(dfs\) 的过程中，如果在回溯到 \(j\) 的时候发现可以删除 \(q\)，那么就删除 \(q\)，并更新 \(j\) 本身的代价，这样可能会导致无法再回溯到 \(i\) 点的时候删除 \(p\)。

粗略想一下这不是有后效性嘛，但是因为贪心删了儿子而导致这个点不能再删，那么我们只会损失一个点，就是该点，而删除儿子至少会删除一个，所以不会亏。。

综上，自底向上的删除无后效性，满足贪心性质。

最后放上代码。BZOJ上A了，垃圾谷上要开\(O_2\)才能A是什么鬼。

#include<bits/stdc++.h>

using namespace std;

int read()

{

    int x=0,w=1;char ch=getchar();

    while(ch>'9'||ch<'0') {if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*w;

}

const int N=2000010;

int n,m,x,cnt,ans;

int head[N],a[N],num[N],sum[N];

struct node{

    int to,next;

}edge[N];

void add(int x,int y)

{

    cnt++;edge[cnt].to=y;edge[cnt].next=head[x];head[x]=cnt;

}

void dfs(int k)

{

    priority_queue<pair<int,int> >q;

    for(int i=head[k];i;i=edge[i].next)

    {

        int v=edge[i].to;

        dfs(v);q.push(make_pair(1-num[v]-a[v],v));

    }

    while(q.size())

    {

        int u=-q.top().first,v=q.top().second;

        if(sum[k]+u<=m) a[k]+=a[v],num[k]+=num[v]-1,sum[k]+=u,ans++,q.pop();

        else break;

    }

}

int main()

{

    n=read();m=read();

    for(int i=0;i<n;i++)a[i]=read();

    for(int i=0;i<n;i++)

    {

        num[i]=read();sum[i]=num[i]+a[i];

        for(int j=1;j<=num[i];j++) x=read(),add(i,x);

    }

    dfs(0);cout<<ans<<endl;

}

巴特西

[HEOI2015]兔子与樱花（贪心）