音乐播放器
HMF-have much fun Site
 
文章 标签
16
✎首页 ✎首页
☰归档 ☰归档
★标签 ★标签
☎关于 ☎关于
♚推荐 ♚推荐
说说 说说
友人帐 友人帐
Powered by Gridea | Theme: Fog
载入天数...
载入时分秒...
总访问量:  |   访问人数:
Copyright © 2020 备案号: 闽ICP备21335467号
阅
2022-03-25
2 min read
CodeForce 题解

【题解】CF1039D You Are Given a Tree

  热度: loading...

审核大大求过

考虑 dpdp ，设 dpidp_i 为从 ii 的子树里延伸到 ii 的最长的链的长度。

对于每个节点，记下子节点里 dpdp 值的最大值和次大值，如果这两个值合并后 大于等于我们需要的长度 kk ，就将其合并，并将 dpidp_i 清零（因为记录的是一端为 ii 的链的长度）可以证明这一定是最优的。

性感的证明：

发现如果在一个地方能够合并的一定会立刻合并，因此还保留在 dpidp_i 里的一定是还不可以合并的，因此在第一个可以合并的点马上合并一定是最优的。

证明了和没证明一样

然后我们有两条路子：

  1. 根号分治

首先把 k≤nk \le \sqrt{n} 的直接 O(n)O(n) 处理掉，发现之后 kk 大于 n\sqrt{n} 的部分答案都小于 n\sqrt{n}， 因此通过二分找出答案相同的一段区间直接赋值，复杂度为 O(nnlog⁡n)O(n\sqrt{n}\log n)

  1. 整体二分

发现随着 kk 的增大答案减小，因此对于一个询问区间，先求出区间中点 midmid 的答案 tottot ，然后左半边的答案范围就在 tot∼ntot \sim n ，右半边的答案范围就在 0∼tot0 \sim tot ，当答案范围缩小到一个数后直接赋值即可。

但这玩意的复杂度好像是假的（我证不出来，如果有大佬证出来可以评论一下打脸我），因此复杂度正确的做法还是和前一种一样，先暴力算出 k≤nk \le \sqrt{n} 的答案，然后在 n+1\sqrt{n}+1 到 nn 的部分整体二分，因为答案只有 n\sqrt{n} 个，分治树只有 lognlog n 层，所以复杂度还是 O(nnlog⁡n)O(n\sqrt{n}\log n) 。 本质相同

大概就是这么多，算是很典的题了。

赏
  • 文章作者：Linky
  • 原文链接：https://lookcatbox.github.io/post/ti-jie-cf1039d-you-are-given-a-tree/
  • 版权声明：本博客所有文章除特别声明外，均采用BY-NC-SA 许可协议。转载请注明出处！