原来想的是给所有点排序。。。。但是要修改啊。。。然后发现对于儿子排序就可以了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define maxn 2000050 #define maxv 2000050 #define maxe 4000050 using namespace std; int n,m,c[maxn],s[maxn],x,top=0,ans=0,g[maxv],nume=1,fath[maxv],tot[maxv]; bool vis[maxn]; struct pnt { int id,rank; }p[maxn]; struct edge { int v,nxt; }e[maxe]; struct value { int val,id; }ret[maxn]; queue <int> q; int read() { char ch;int data=0; while (ch<'0' || ch>'9') ch=getchar(); while (ch>='0' && ch<='9') { data=data*10+ch-'0'; ch=getchar(); } return data; } bool cmp1(pnt x,pnt y) {return x.rank<y.rank;} bool cmp2(value x,value y) {return x.val<y.val;} void addedge(int u,int v) { e[++nume].v=v; e[nume].nxt=g[u]; g[u]=nume; } void topusort() { p[1].id=1;p[1].rank=0;q.push(1); while (!q.empty()) { int head=q.front();q.pop(); for (int i=g[head];i;i=e[i].nxt) { int v=e[i].v; p[v].id=v;p[v].rank=p[head].rank+1; q.push(v); } } sort(p+1,p+n+1,cmp1); } int main() { n=read();m=read(); for (int i=1;i<=n;i++) c[i]=read(); for (int i=1;i<=n;i++) { s[i]=read(); for (int j=1;j<=s[i];j++) { x=read();x++; addedge(i,x);fath[x]=i;tot[i]+=c[x]; } } topusort(); for (int i=n;i>=1;i--) { top=0;int now=p[i].id; for (int j=g[now];j;j=e[j].nxt) { int v=e[j].v; ret[++top].val=c[v]+s[v]-1; ret[top].id=v; } sort(ret+1,ret+top+1,cmp2); for (int j=1;j<=top;j++) { if (c[now]+s[now]+ret[j].val<=m) { ans++; tot[now]+=tot[ret[j].id]; c[now]+=c[ret[j].id]; s[now]+=s[ret[j].id]-1; } } } printf("%d ",ans); return 0; }