当前位置: 首页 > news >正文

树形dp [POI 2013] LUK-Triumphal arch

波兰人神秘题目。

题意

\(n\) 点的树,初始节点 1 为黑色,其余白色。

两个人在博弈。

B 一开始位于 1 点,进行如下的回合。

首先每轮 A 选择 K 个点,然后 B 选择一个相邻的节点进行移动。

若任意时刻 B 位于白色的节点则 B 获胜。

若 A 将点全染黑 A 胜利。

求最小的 K 使得 A 可以获胜。

\(N\) 是 1e5 级别的。

做法

我上来就写了一个贪心,后来想想是假的,这里不提了,反正得分还挺高。

这个 K 明显有单调性,所以二分 K,尝试转换为一个判断问题。

先说结论,B 不可以走回头路。

因为 A 自然会堵死每一个 B 到过的节点,这并没有任何意义,相当于多给了 A 一次染色的机会,完全是愚蠢的。

所以 B 只能一条路走到黑。

A 每一次首先肯定是要先染自己所有的子节点,如果不够就需要之前的剩余进行弥补。

发现这个过程实际上是在合并所有子树的所需,加上自身的所需向上传(虽然可能是负数就对了)。

进而我们考虑树形 dp。

我们设 dp[u] 表示 u 子树所需要的之前的染色次数的总量。

son[u] 表示 u 的子节点数量。

不难得出 \(dp[u]=son[u]-k+\sum_{v是u子节点}^{}max(dp[v],0)\)

注意这里需要取 max, 我一开始并没有考虑到,因为子树的次数是不可能向上贡献的。

我们只需要检查 dp[1]<=0 就行的。

时间复杂度 \(O(nlogn)\),二分的值域和 n 一样,不做区分了。

代码如下

点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MN=1e6+116;
struct Node{int nxt, to;
}node[MN];
int head[MN], tottt;
void insert(int u, int v){node[++tottt].to=v;node[tottt].nxt=head[u];head[u]=tottt; return;
}
int n, son[MN], dp[MN], ans;
void Read(){cin>>n;for(int i=1,u,v; i<n; ++i){cin>>u>>v; insert(u,v); insert(v,u);}
}
void Pre_dfs(int u, int father){for(int i=head[u];i;i=node[i].nxt){int v=node[i].to;if(v==father) continue;son[u]++; Pre_dfs(v,u);}
}
void dfs(int u, int father, int k){dp[u]=son[u]-k;for(int i=head[u];i;i=node[i].nxt){int v=node[i].to;if(v==father) continue;dfs(v,u,k);dp[u]+=max(dp[v],0);}
}
bool judge(int k){for(int i=1; i<=n; ++i) dp[i]=0;dfs(1,1,k); return dp[1]<=0;
}
void binary(){int l=0, r=3000001; ans=3000001;while(l<=r){int mid=(l+r)>>1;if(judge(mid)){ans=mid; r=mid-1;}else{l=mid+1;}}
}
void print(){cout<<ans<<'\n';
}
void solve(){Read(); Pre_dfs(1,1);binary(); print();
}
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);solve();return 0;
}
http://www.hskmm.com/?act=detail&tid=20878

相关文章:

  • 【论术】t-design tree组件判断点击了角标还是label
  • leetCode刷题记录1
  • k8s下部署kuboard
  • ACL 第一周模拟赛题解
  • 万象EXCEL开发(三)格式解读calcChain.xml——东方仙盟练气期 - 指南
  • 302、寄门人
  • 达梦数据库用户开启限制白名单导致自身无法登录
  • 【转发】Nginx配置https
  • 本地文件多人多端同步工具:10款高性价比选择
  • 打破AI孤岛:CIO集成实战指南
  • 密码学学习记录(四)
  • Sharding-Proxy、ShardingSphere 和 Sharding-JDBC区别
  • echarts4升级为echarts5的常见问题
  • ISO 周计算 记录
  • 从 “被动耗能” 到 “主动优化”:MyEMS 开启商业建筑能源管理 “新范式”
  • 【故障排查】视频汇聚EasyCVR接入设备通道数为0?通道编码长度不规范导致
  • 来信小程序管理系统:匿名信息传递与社交互动平台
  • PCIe加速卡设计资料:416-基于Kintex Ultrasacle的万兆网络光纤 PCIe加速卡
  • 多生产者,多消费者
  • GEO优化实战指南:一周内让豆包、Deepseek、Kimi等推荐了我的插件
  • 房产楼盘小程序管理系统:助力房产营销数字化升级的优质解决方案
  • 高速信号处理设计方案:413-基于双XCVU9P+C6678的100G光纤加速卡
  • Teamcenter:结构管理器查询(又称:BOM结构查询)
  • 2025年最好用的同步云盘是哪个?一个老用户的真实体验分享
  • 使用 ShedLock 实现多实例定时任务单执行的常见错误及解决办法
  • 1_二分查找
  • AI元人文:悟空博弈专用芯片
  • 【ACM出版】第五届管理科学和软件工程国际学术会议(ICMSSE 2025)
  • PiXYZ Studio 2021下载地址与安装教程
  • coremail日常操作