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

树形dp [JOI Open 2020] 发电站 / Power Plant

作为最强摸鱼人的 BaiBaiShaFeng,这个题解也是发到洛谷上了,希望给过。

先辈们说的太简略了我感觉有点难懂,虽然我的表达能力很弱,估计强不了多少。

注:参考过网上零散题解。

题意很好理解,我们就不过多叙述了。

不看炸掉的机子,我们实际上是在选择一个联通块去覆盖树的一部分,而我们所要求的就是这个联通块的最大值。

我们统一在这个联通快的最高点进行答案的统计,从子树的贡献向上递归,这个样子问题可以从子树中合并上来,进而考虑树形 dp。

\(dp[u]\) 表示联通块的最高点还在祖先处时 \(u\) 子树中的答案,形象的说,就是上不封顶。

这个时候我们只要选择了 \(u\) 子树中的发电机 \(u\) 自然会炸,因为最高点在祖先,上边会有其他启动的发电机。

所以我们一共有两种决策:选择所有子树中的最佳情况或者干脆不选子树,去选 \(u\) 上的发电机。

注意如果没有发电机便只有第一种情况。

明显不存在其他情况。

转移于是乎就明显起来了,我们在 \(\sum_{v\in son[u]} dp[v]-1\)\(1\) 之间取最大就是 \(dp[u]\) 了。

这个式子对应了我们上边说的两种情况,下边说说答案的统计。

我们规定了在最高点统计答案,每个点都可以是最高点,对于一个最高点,若不想让这个点炸只能选择一个子树中的答案,若允许它炸就直接选择所有子树中的答案再让它炸,第二种和 \(dp[u]\) 最终的结果应该是相等的,但是含义并不一样,后边为了方便写在一起了。

代码如下,这个题想起来有些麻烦但实现起来就很轻松。

#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, dp[MN], has[MN], ans=0;//has表示介个点有没有发电机
void Read(){memset(dp,0,sizeof(dp)); memset(has,false,sizeof(dp));cin>>n;for(int i=1,u,v; i<n; ++i){cin>>u>>v; insert(u,v); insert(v,u);}string s; cin>>s; s=' '+s;for(int i=1; i<=n; ++i){if(s[i]=='1') has[i]=true;}
}
void dfs(int u, int father){for(int i=head[u];i;i=node[i].nxt){int v=node[i].to;if(v==father) continue;dfs(v,u); dp[u]+=dp[v];ans=max(ans,dp[v]+(has[u]));//最高点不炸,选择一棵子树}if(has[u]) dp[u]=max(dp[u]-1,1);ans=max(ans,dp[u]);//最高点可炸
}
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);Read(); dfs(1,1); cout<<ans<<'\n';return 0;
}

若有不足请告诉我,谢谢啦。

http://www.zskr.cn/news/14067.html

相关文章:

  • DeepSeek-V3.2-Exp 完整分析:2025年AI模型突破与稀疏注意力技术深度解析
  • Java EE初阶启程记05---线程安全 - 指南
  • 解码数据结构队列
  • 解决升级 Windows 11 24H2 后 NAS 共享无法显示的问题
  • 【还未找到原题】宝石(GEM) - Harvey
  • Android 系统源码级进程保活全方案:从进程创建到后台防护 - 实践
  • 微信群机器人API
  • 【CF19E】Fairy - Harvey
  • 软件工程中线性回归应用
  • 构建移动网关:Air780EPM用4G为WiFi和LAN设备供网
  • 2025年人工智能与智能装备国际学术会议(AIIE 2025)
  • 详细介绍:衡石HQL深度解析:如何用类SQL语法实现跨源数据的高效联邦查询?
  • Java 类类型
  • 9月29日
  • 国内信创领域的PostgreSQL技术能力认证
  • redis-AOF持久化机制
  • 03-控制台项目创建与结构说明
  • ttkefu2026迎来永久免费的客服系统分享
  • 002- 学习环境搭建
  • 求局部最小值
  • Element-UI的transfer穿梭框组件数据量大解决方案
  • 【软件系统架构】系列七:系统性能——操作系统性能深入解析 - 实践
  • Linux 生成随机端口
  • 并发编程可见性
  • VsCode Ai插件
  • 写入方式、COW 与写放大
  • 黄金分割比
  • how create rhel8 local repository server
  • 借助Aspose.Email,使用 Python 读取 Outlook MSG 文件
  • 文件同步工具深度测评(2025版):同步盘夺冠