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

AT_agc052_b [AGC052B] Tree Edges XOR

考虑边权转点权,让边权满足其为相邻点权的异或和,操作变成交换两个点的点权。

随便钦定一个为根,设 d
i

为初始时 i 的点权,f
i

是 i 期望得到为多少。如果存在 d,f,满足它们是相同的集合,就有解。

注意到如果确定了一个点的点权,那么其他所有点权都能唯一的确定。

现在钦定 f
i

为 i 到根路径上的边权和(或者说钦定 f
1

=0),注意到任何一组解都能把所有点权异或 f
1

,得到 f
1

=0 的解,所以判断是否有解就判断 f
1

=0 的时候是否有解。

现在 f 确定了,看是否存在 d,满足 d 和 f 是相同的集合。

现在继续钦定 d
i

为 i 到根路径上边权和,与 f 相同,所有可能为答案的 d

都是 d 异或上一个 x 得到的。

那么有解的必要条件就是 (d
1

⊕x)⊕(d
2

⊕x)⊕...⊕(d
n

⊕x)=f
1

⊕f
2

⊕...⊕f
n

,由于 n 为奇数,所以可以解出 x 是多少。

由于这仅是必要条件,那么最后还要 check 一下是否合法。

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

相关文章:

  • 背单词 纯英文 2025年10月
  • 英语背单词 专八词汇 中英对照 2025年10月
  • 「Diary Solution Set」October 2025 在凉雨停歇的那天
  • macOS Tahoe All In One
  • 风力发电机输出功率模型综述 - 详解
  • 2025年小红书创作者影响力分析报告:基于10.5万条素材构建评估模型,识别高影响力内容特征,优化推荐算法与运营策略,涵盖用户分层、互动数据、地理位置分布,提供内容策略优化与创作者成长建议。
  • MaopaiJD Esp8266 代码
  • 英语_错题集_25-10
  • 公民科学研究奖项众人智慧表彰技术创新项目
  • 25.10.1随笔联考总结
  • C# WPF {x:Reference}的作用
  • Ynoi Easy Round 2015 学习笔记
  • 1数学建模模型分类
  • 数学每日?题
  • 最大公约数和最小公倍数
  • OpenSpeedy最新版下载,夸克百度网盘加速提速|游戏加速工具|官网入口
  • Nginx核心配备详解:访问控制、用户认证与HTTPS部署
  • 5. 最长回文子串
  • 基于Python+Vue开发的婚恋交友管理系统源码+运行步骤
  • 2025 年搅拌机设备厂家 TOP 企业品牌推荐排行榜,盘点磁混凝系统 / 发酵罐 / 刮泥机 / 推进式 / 脱硫侧搅拌机公司推荐!
  • 福州市 2025 国庆集训 Day1 前三题题解
  • Python常用数据类型详解:字符串、列表、字典全解析
  • 强连通,Tarjan,缩点
  • OI 笑传 #13
  • Python方案--交互式VR教育应用开发
  • 纯Qt代码实现onvif协议设备端/onvif设备模拟器/onvif虚拟监控设备/桌面转onvif
  • *补*““逆元求组合数”(费马小定理
  • C# WPF中Binding的 Source属性和ElementName属性有什么区别
  • Typora to Obsidian 迁移助手 (Typora-to-Obsidian-Migration-Helper)
  • 64. 最小路径和