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

洛谷 P3233

给定一棵有 \(n\) 个节点的树和 \(T\) 组询问。每组询问给定 \(m\) 个关键点,设 \(f(y)\) 表示离 \(y\) 最近的关键点(多个取编号最小。)请回答对于每个关键点 \(x\),有多少个 \(f(y) = x\)

\(n, \sum m \le 3 \times 10^5\)

这种问题一看就是要建出虚树的。建完虚树后可以先求出虚树上的点的 \(f(y)\) 以及距离 \(dis(y)\)(使用换根即可)。对于一条虚树上的边 \(u, v\),肯定是被划分成两部分,一部分的 \(f(y) = f(u)\),另一部分为 \(f(y) = f(v)\),可以根据 \(dis(u), dis(v)\) 找出这个分界点,然后用子树大小算一下贡献即可。可能要特判下 \(f(u) = f(v)\) 的情况。

时间复杂度:\(O(\sum m \log m)\)

http://www.gsyq.cn/news/42170.html

相关文章:

  • 组件理解
  • “模型法线到视图法线”的变换矩阵(normal matrix)的计算和作用
  • 去年夏天
  • aspose-pdf 修改pdf文件备忘录
  • 函数名与函数地址的关系(函数指针)
  • 别再选错!5分钟掌握AI Agent框架选型的方法
  • Linux - 7 磁盘管理篇
  • Markdown之Typora语法
  • markdown入门(复盘)
  • 卡尔算法哈希表
  • Rust 之二 各组件工具的源码、构建、配置、使用 - 教程
  • 新东方听力day2
  • 超级管理员目录索引的Google搜索技巧
  • 无限欢愉 深入推进 我沦陷在那片故地 我渴饮着 你的呼吸 却得不到 你的心
  • 基础架构
  • Word表格1.5倍行距居中问题
  • 详细介绍:后端_Redis 分布式锁实现指南
  • 日总结 23
  • [题解]P10277 [USACO24OPEN] Bessies Interview S
  • UE:论运行时动画录制的关键-正确获取骨骼数据与保存
  • 线性基相关
  • 低代码权限管理安全合规指南:守住数据安全的 “最后一道防线”
  • 2025-11-06
  • 关于waybar状态栏颜文字乱码问题
  • P10277 [USACO24OPEN] Bessies Interview S 题解
  • AI 时代的数据库进化论 —— 从向量到混合检索
  • vue 3.x 前端导出功能
  • 最高法-合同目的的认定
  • 2025年恒温恒湿机标杆厂家最新推荐:中焓环境,档案室恒湿机/精密恒温恒湿机/吊顶恒温恒湿机/档案室恒温恒湿机,定义环境控制精准新标准
  • 酸角糕行业发展趋势解析:2025年十大品牌综合测评与选择指南