鬼能想到是个贪心。明明觉得是树规啊。。又完美爆零。。

从叶子节点往上更新,能保证最优解(这块想了半天)。

证明:当你的子树上有能删的点而你不删时,可能会对子树的根节点有利,最好的情况是使子树根节点由不可删除变为可删除。但是,既然最终可能删一个点,还不如直接删现成能删的呢。。

用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;
}

  

最新文章

  1. string和char*的相互转换
  2. 一个android样本的过保护
  3. IOS 杂笔- 6(KVC-KVO)
  4. eclipse字体的设置
  5. 离线安装Android开发环境的方法
  6. 车牌识别LPR(三)-- LPR系统整体结构
  7. php文件上传大小限制的修改方法大全
  8. VB execl文件后台代码,基础语法
  9. leetcode_question_85 Largest Rectangle in Histogram
  10. SQL求解两个时间差
  11. [luoguP2912] [USACO08OCT]牧场散步Pasture Walking(lca)
  12. 【USACO Mar08】 奶牛跑步 A-star k短路
  13. Linux连接虚拟机及操作指令
  14. 安装Redis 4.0单实例
  15. day60 pymysql
  16. MySQL表与表之间的关系详解
  17. 用面向对象计算BMI指数
  18. Go语言学习之3 流程控制、函数
  19. AIX查看CPU、内存等信息
  20. Ios8 Xcode6 设置Launch Image 启动图片

热门文章

  1. 一张图告诉你angular2所有知识点
  2. Centos操作系统在虚拟机VMware上的安装
  3. Perl初试
  4. ubuntu主机名修改
  5. 工厂设计模式 Factory
  6. 交叉编译 tesseract
  7. JavaScript一个鼠标滚动事件的实例
  8. Html table 合并单元格
  9. sql操作一般函数
  10. (转)Eclipse快捷键 10个最有用的快捷键