1. 首页
  2. 数据库
  3. 其它
  4. CF1336 A. Linova and Kingdom

CF1336 A. Linova and Kingdom

上传者: 2021-01-08 04:30:02上传 PDF文件 42.42KB 热度 9次
A. Linova and Kingdom 题意 给你一颗nnn个节点根为1号节点的树,选kkk个城市作为工业城市,其余为旅游城市,工业城市的使节每经过旅游城市开心值+1,求所有工业城市的使节到1号节点的开心值的和最大为多少? 思路 贪心 dfs 很容易看出来如果只选一个,一定选距离根节点最远的叶子,我们思考第四个为什么选2而不是3和4,因为选3和4,会减少其子树节点的开心值。(因为我们选这个点,根据贪心我们肯定已经选了所有他子树的节点) 每个结点的贡献值=到根节点的距离−子树的节点数每个结点的贡献值=到根节点的距离-子树的节点数每个结点的贡献值=到根节点的距离−子树的节点数 我们求出每个节
下载地址
用户评论