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

题解:P9454 [ZSHOI-R1] 巡城

题目:

\(1\) 出发,求期望 dfn 序。

\(1\) 点很特殊,先固定 \(1\) 点,发现去除 \(1\) 后是森林,而 \(1\) 把他们都连起来了。

先固定一棵树的一个根 \(rt\),思考这时 \(x\) 点的期望 dfn 序会被三种点贡献:

  • \(rt→x\) 每个点贡献 \(1\)
  • \(x\) 子树内每个点贡献 \(0\)
  • 其他节点贡献 \(\frac{2}{1}\)
    最后一个有点反直觉证一下:
    假设 \(v\) 为其他节点,\(x\)\(v\) 相对顺序只有两种,手玩一下就知道了。

然后再固定一棵树的另外一个根

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

相关文章:

  • QuestaSim奔溃后再次打开无法仿真
  • 软考架构备考-软件可靠性、知识产权和标准化
  • 医院内外网文件传输:平衡安全与效率的关键链路!
  • 我的第一个赚钱网站 -- 从网站源码到集成AdSense获利的全过程
  • Gradle读取仓库配置文件的优先级
  • opencv学习记录5
  • PCS PMA,如何理解硬核IP
  • pycharm中使用调试模式运行 uvicorn.run(app)报错TypeError: _patch_asyncio.locals.run() got an unexpected keywor解决
  • 交换机命令
  • 2025.9.25
  • 易基因:Cell Rep:华农任文凯团队利用ChIP-seq及多组学解析过敏性疾病的关键调控机制|项目文章
  • 详细介绍:STL 容器 --- list 类
  • Idea代码回退已经push到远段仓库的代码分支到指定提交记录
  • 开写第一篇
  • 大模型function calling多轮对话开发示例
  • ViTables 安装与 HDF5 数据可视化全指南 - 实践
  • elementuiplus修改el-checked多选框样式
  • DataGrip格式化SQL模板
  • 计算机毕设java毕业生档案流向追踪系统的设计与实现 基于Java的毕业生档案管理与追踪系统的设计与实现 Java技术驱动的毕业生档案流向监测架构开发
  • 图思维胜过链式思维:JGraphlet构建任务流水线的八大核心原则
  • 两月九城,纷享销客渠道携手伙伴共创CRM新纪元
  • markdown
  • mstsc带用户名密码自动登录
  • Sql Server Begin TRY sample
  • 基于数据平台构建供应链协同体系,实现业务全链路可视化与智能决策
  • 字节二面挂!面试官追问 Redis 内存淘汰策略 LRU 和传统 LRU 差异,我答懵了
  • UPX压缩工具的用法
  • NM:微生物组数据分析的规划与描述 - 详解
  • 300、金陵图
  • 山东布谷鸟科技:助力教育培训软件开发数字化转型与高效管理