鬼能想到是个贪心。明明觉得是树规啊。。又完美爆零。。
从叶子节点往上更新,能保证最优解(这块想了半天)。
证明:当你的子树上有能删的点而你不删时,可能会对子树的根节点有利,最好的情况是使子树根节点由不可删除变为可删除。但是,既然最终可能删一个点,还不如直接删现成能删的呢。。
用wei[]记录每个节点的权值(花数+儿子数),在更新结果时将权值更新即可。
#include #include #include #include #include #include using namespace std; #define pos(i,a,b) for(int i=(a);i<=(b);i++) #define N 2000500 int n,m; vector son[N]; int wei[N]; int ji[N]; int ans; bool tmp(const int &a,const int &b) { return wei[a] } void dp(int x) { if(ji[x]==0) return; pos(i,0,ji[x]-1) { dp(son[x][i]); } sort(son[x].begin(),son[x].end(),tmp); pos(i,0,ji[x]-1) { if(wei[x]-1+wei[son[x][i]]<=m) { ans++; wei[x]+=wei[son[x][i]]-1; } } } int main() { freopen("sakura.in","r",stdin); freopen("sakura.out","w",stdout); cin>>n>>m; pos(i,1,n) scanf("%d",&wei[i]); pos(i,1,n) { scanf("%d",&ji[i]); wei[i]+=ji[i]; pos(j,1,ji[i]) { int p; scanf("%d",&p); p++; son[i].push_back(p); } } dp(1); cout<<ans; //while(1); return 0; }