mxh带窝补省选

OI 省选 mxh带窝飞

HEOI2015

兔子与樱花

出师不利

从下向上贪心合并。

时间复杂度$O(N\log N)$。

# include <cstdio>
# include <algorithm>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; i ++)
const int NR = 2001000;
pair <int, int> a[NR];
int deg[NR], bg[NR], c[NR], n, m, ans;
# define v a[bg[x] + i].second
void DFS (int x)
{
    REP (i, deg[x]) DFS (v);
    REP (i, deg[x]) a[bg[x] + i] = make_pair (c[v], v);
    sort (a + bg[x] + 1, a + bg[x] + deg[x] + 1);
    REP (i, deg[x]) if (c[x] + c[v] - 1 <= m) c[x] += c[v] - 1, ans ++;
}
int main ()
{
    scanf ("%d%d", &n, &m);
    REP (i, n) scanf ("%d", &c[i]);
    int sz = 0, t1;
    REP (i, n)
    {
        scanf ("%d", &deg[i]), bg[i] = sz, c[i] += deg[i];
        REP (j, deg[i]) scanf ("%d", &t1), a[sz + j] = make_pair (0, t1 + 1);
        sz += deg[i];
    }
    DFS (1);
    printf ("%d\n", ans);
    return 0;
}