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

CF1918F Caterpillar on a Tree

题目大意:

有一棵 \(n\) 个节点的树,你初始在 \(1\) 节点,每次你可以选择以下某一步。

  1. 移到与 \(x\) 相邻的点,花费 \(1\) 的时间。
  2. 移到 \(1\),不花费时间。
    第二种操作最多执行 \(k\) 次,求最小遍历完整棵树的时间。
    \(n \le 2 \times 10^5, k \le 10^9\)

解题思路:

首先没有二操作的话直接就是 \(2 \times (n - 1) - maxdep\)
考虑过程是怎样的,显然就是每个边进去一次出来一次,最后停在深度最深的点即可。

那么对于二操作。
考虑一个点 \(u \to v\),如果对他使用第二种操作,那么从 \(u->lca\) 的距离就变成了 \(1->lca\) 的距离。
那么只需要通过调整选最大的 \(k\) 个即可。

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

相关文章:

  • tryhackme-预安全-网络如何工作-DNS 详细信息-09
  • Diffusion
  • SP4191 天空代码 分析
  • l2正则化项以及torch.norm
  • 又数据结构
  • 大物实验
  • 蒙特卡洛保形预测技术解析
  • [KaibaMath]1013 关于收敛数列保不等式性的证明
  • 20231408徐钰涵《密码系统设计》
  • 洛谷比赛做题记录
  • 什么是命运(摘抄)
  • 编程指北的 C++
  • Linux grep命令
  • 物品复活软件开发记录 - CelestialZ
  • 螺纹钢的中线节奏
  • 2022 ICPC Hangzhou
  • KL散度
  • Win11常用的bat脚本
  • 随便记
  • Map与Map.Entry的区别
  • 真诚
  • 历史和线段树
  • 大数据分析之MySQL学习2
  • [KaibaMath]1012 关于收敛数列保号性的推论的证明
  • 申公豹说
  • 赛前训练 12 树的直径、中心和重心
  • 关于无人巡航小车的学习笔记
  • 详细介绍:springboot+vue智慧旅游管理小程序(源码+文档+调试+基础修改+答疑)
  • 存算一体架构的先行者:RustFS在异构计算环境下的探索与实践
  • 2-SAT