[HEOI 2015]うさぎとさくら
3990 ワード
私を馬鹿にして,問題を間違えた.
1つのノードに対して、できるだけ選択できるなら、1つのサブノードを選択する代価はc[v]+lson[v]ソート貪欲で、ツリー型DPでよい.
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;
}