[HEOI 2015]うさぎとさくら

3990 ワード

私を馬鹿にして,問題を間違えた.
1つのノードに対して、できるだけ選択できるなら、1つのサブノードを選択する代価はc[v]+lson[v]ソート貪欲で、ツリー型DPでよい.
#include 
#include 

using namespace std;

const int SN = 2000000 + 10;

int c[SN], n, head[SN], ans, num, x, u,tmp[SN], cnt, m, s[SN];

struct Edge {
    int from,to,next;
}E[SN<<1];

void Read(int &x) {
    int in = 0,f = 1;char ch = getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') f = -1;ch = getchar();}
    while(ch>='0' && ch<='9') {in = in*10+ch-'0';ch = getchar();}
    x = in*f;
}

void Add(int u,int v) {
    E[++num].from = u;
    E[num].to = v;
    E[num].next = head[u];
    head[u] = num;
}

void dfs(int u,int fa) {

    for(int i = head[u]; i; i = E[i].next) {
        int to = E[i].to;
        if(to == fa)    continue;
        dfs(to,u);
    }

    cnt = 0;
    for(int i = head[u]; i; i = E[i].next) {
        tmp[++cnt] = c[E[i].to]-1; //      ,       1
        //WA   ,      lson[]     
    }

    c[u] += cnt;

    sort(tmp+1,tmp+cnt+1);

    for(int i = 1; i <= cnt; i++) {
        if(c[u] + tmp[i] <= m) {
            c[u] += tmp[i];
            ans++;
        }
        else break;
    }
}

int main() {

    Read(n),Read(m);

    for(int i = 0; i < n; i++) {
        Read(c[i]);s[n] = c[i];
    }

    for(int i = 0; i < n; i++) {
        Read(x);
        for(int j = 1; j <= x; j++) {
            Read(u);
            Add(i,u);
        }
    }

    dfs(0,-1);

    printf("%d
"
,ans); return 0; }