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

P9745 「KDOI-06-S」树上异或

很有教育意义的树形DP,看起来很典,但我没见过

首先考虑链的情况,设 \(f_i\) 表示前 \(i\) 个点,所有删边方案中,所有联通块点权异或和的乘积的和,其实就是一个 \(\sum \prod\) 的形式,这样我们枚举最后一个连通块就可以转移了:\(f_i = \sum_{j<,i} f_j \times \oplus_{k=j+1}^i x_k\)。这样转移是 \(O(n)\) 的,总复杂度 \(O(n^2)\),考虑优化。

我们希望 \(O(1)\) 转移,上面的式子复杂度高,究其原因是需要枚举转移点,这样的跳跃式转移要避免,考虑连续地转移。

异或和其他运算没什么性质,直接拆位,设 \(g_{i,j,k}\) 表示包含 \(i\) 的连通块权值的第 \(j\) 位为 \(k\) 的所有方案中,不包含 \(i\) 的连通块权值的乘积的和。初始时若 \(x_i\)\(j\) 位为 1,则 \(g_{i,j,1}=1\),否则 \(g_{i,j,0}=1\)。转移

\[g_{i,j,1} = g_{i,j,1}\times (g_{i-1,j,0}+f_{i-1})+g_{i,j,0}\times g_{i-1,j,1} \]

\[g_{i,j,0} = g_{i,j,1}\times g_{i-1,j,1}+g_{i,j,0}\times (g_{i-1,j,1}+f_{i-1}) \]

\[f_i=\sum_{j=0}^{63}2^j\times g_{i,j,1} \]

把这个搬到树上是一样的,答案是 \(f_1\)

上面转移时要加 \(f_{i-1}\) 是因为 \(g_{i-1,j,k}\) 钦定了包含 \(i-1\),实际上不包含的也要算进去,这点在序列上看不出来,但在树上是很关键的,因为树上的连通块有多个分支,而序列上只有一个。

http://www.hskmm.com/?act=detail&tid=34891

相关文章:

  • P9523 [JOISC 2022] 复制粘贴 3
  • 2025年10月高端奢侈家电品牌推荐排行榜:五大品牌综合对比与选购
  • P3147 [USACO16OPEN] 262144 P
  • 智能交付时代:国内企业如何选择最适合的CI/CD工具?
  • 吴恩达深度学习课程一:神经网络和深度学习 第三周:浅层神经网络(三)
  • 2025 年最新彩钢瓦厂家推荐排行榜:屋顶 / 防水 / 屋面等优质产品精选压型 /0.5 厚/屋面/墙面彩钢瓦公司推荐
  • 结对项目--实现一个自动生成小学四则运算题目的命令行程序
  • LCA
  • 【测试分类 (下)】测试分类看这篇就够了:彻底告别概念混淆,轻松搞定工作面试 - 指南
  • 树状数组
  • 如何管控文件外发安全,确保企业数据不被泄露
  • 打通CI/CD最后一公里:制品库如何成为高效流水线的核心枢纽
  • 2025年10月高端奢侈家电品牌推荐排行榜及深度对比分析
  • 嵌入式调式方案:
  • 2025年10月高端奢侈家电品牌推荐排行榜对比与深度评测分析
  • 2025年GEO品牌推荐排行榜前十强权威发布
  • 2025年GEO品牌推荐榜与排行榜Top10:权威解析与行业洞察
  • 2025年10月高端奢侈家电品牌推荐排行榜单对比与评测分析
  • 第五章 linux实战-CMS01
  • 字典树
  • 2025年10月高端奢侈家电品牌推荐排行榜:五大品牌综合对比与选购指南
  • mysql 更新默认时间
  • A. Vasya and Petyas Game
  • Android Studio Archive | Android Studio 归档下载
  • 关系型数据库的基本理论
  • JAVA集合
  • 【最新推荐】分享十大常用又靠谱的文件摆渡系统
  • C语言实现LDPC码译码功能
  • 2025年10月中国试验机厂家推荐:十强榜单对比与性能评测
  • [NOIP 2012 提高组] 开车旅行 的AC代码