BZOJ 4027 HEOI2015 兔子與櫻花 樹形貪心

題目大意：給定一棵有根樹，每個點上有一些櫻花，現在要求刪除一些節點，刪除節點的櫻花和子節點都會連到父節點上，要求每個節點的櫻花數+子節點數不超過m，求最多刪多少個節點

這數據范圍也只能貪心了吧= =
令fi為以節點i為根的子樹中能刪除的最多節點(i節點不刪)，gi為刪除最多節點的情況下i號節點的最小負重
那麼首先對於每個節點我們對於所有的子節點為根的子樹盡量刪，然後考慮如何刪除子節點
對於節點x以及x的子節點y，若刪除y節點，對gx的貢獻為gy?1
因此我們對x節點的所有子節點按gy?1排序，從小到大取即可

為什麼這是對的呢？
我們考慮一棵子樹對父節點的影響只有刪除子樹的根時根上的東西會被塞到父節點上去
那麼一棵子樹如果刪的不是最多，那麼能產生的好處只有刪除根時塞到父親節點上的東西少一些
這樣做的最終收益只有【根節點由不可刪變為可刪】
結果我還莫不如不刪根節點，然後讓子樹中多刪一些呢= =

因此貪心是對的。

#include 
#include 
#include 
#include 
#define M 2002002
using namespace std;
struct abcd{
    int to,next;
}table[M];
int head[M],tot;
int n,m;
int a[M],f[M],g[M];
bool not_root[M];
void Add(int x,int y)
{
    table[++tot].to=y;
    table[tot].next=head[x];
    head[x]=tot;
}
void Tree_Greedy(int x)
{
    int i,top=0;
    for(i=head[x];i;i=table[i].next)
    {
        Tree_Greedy(table[i].to);
        f[x]+=f[table[i].to];
        g[x]++;
    }
    static int stack[M];
    g[x]+=a[x];
    for(i=head[x];i;i=table[i].next)
        stack[++top]=g[table[i].to]-1;
    sort(stack+1,stack+top+1);
    for(i=1;i<=top;i++)
        if(g[x]+stack[i]<=m)
            f[x]++,g[x]+=stack[i];
        else
            break;
}
int main()
{
    int i,j,k,x;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&k);
        for(j=1;j<=k;j++)
        {
            scanf("%d",&x);
            Add(i,++x);
            not_root[x]=true;
        }
    }
    for(i=1;i<=n;i++)
        if(!not_root[i])
        {
            Tree_Greedy(i);
            cout<