BZOJ 4027欲張り

ノードを削除する場合、父親への影響はc[x]+child[x]です.また、影響の小さい点を優先的に選択すると、削除できるなら削除します.削除できるのに削除していないので、父ノードに戻った後、より良い削除方法がなく、影響を小さくすることはありません.
初めてC 4 Droidのコードでフォーマットします.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,j,k) for(i=j;i<k;i++)
const int N = 2000005;
int m, ans, c[N];
vector < int >g[N];
bool cmp(int a, int b)
{
    return c[a] < c[b];
}

void dfs(int x)
{
    int i;
    rep(i, 0, g[x].size())dfs(g[x][i]);
    sort(g[x].begin(), g[x].end(), cmp);
    c[x] += g[x].size();
    rep(i, 0, g[x].size())
    {
        int t = c[g[x][i]];
        if (c[x] + t - 1 <= m)
            c[x] += t - 1, ++ans;
        else
            break;
    }
}

int main()
{
    int n, i, j, y;
    scanf("%d%d", &n, &m);
    rep(i, 0, n) scanf("%d", &c[i]);
    rep(i, 0, n)
    {
        scanf("%d", &j);
        while (j--)
        {
            scanf("%d", &y);
            g[i].push_back(y);
        }
    }
    dfs(0);
    printf("%d", ans);
    return 0;
}