偏门的知识点,但是很好玩啊
前置知识
树的直径
定义:
树上最长的链
适用范围:
显然:树
求解方式:
- 从任意一个点DFS并且存下到每个点到这个点的距离
- 然后从距离最远的那个点又DFS一遍,这次找到的最大的距离就是直径
:但是,还有一个问题:怎么存下来直径上的每一个点(任意一条)
- 其实也很简单,在第二遍的DFS时保存每个点的Father
- 然后从最后找到的那个远点一直找Father并且把每个点统计起来就是了
算法主体
问题描述
给定一颗树(无根)
求一条路径,使得其他点到这条路径的最大距离最小$(n<=300000)$,并且使得这条路径的长度$\le s$
算法分析
暴力
呵呵
分析一波
显然,这条路径肯定在直径上(感性证明)
然后呢?
- 直径上每一个点记能延伸出去的最长距离为$f[x]$
那么显然,对于选定路径x到y:
我们定义:$u\in(x,y)$,$s$为直径起点,$t$为直径终点
于是我们就得到了$n^2$的算法
然而:$n<=300000$
所以我们需要一个$O(n)$的算法
最终算法
其实很简单,我们有两个优化:
优化1:
我们不需要与每一个$f[u]$比较,而是直接与所有$f[u]$的最大值$fmax$比较
然而正确性?
设
$fmax$是由点$p$延伸出来的
$s,t$分别是直径的起点与终点
那么我们可以分为两种情况:
况1:
$p\in(x,y)$
这很显然正确,因为它和之前没有任何区别
况2:
$p\notin(x,y)$
这个时候明显$len(s,x)\ge fmax$或$len(y,t)\ge fmax$
为什么?
我们采用反证
假设$len(s,x)\le fmax$或$len(y,t)\le fmax$
那么明显直径应该以延伸到$fmax$那一条链上,假设不成立
综上:
我们可以直接和$fmax$比较,而不是每次都和$n$个比较
得证:)
优化2:
明显当一条链延长的时候它的解只可能变得更优
证明就免了吧
经过$sun123zxy$的反复询问我还是把证明写出来吧:
况1:
当前的最大值是从$x$或$y$并且在直径上扩展出去的
那么当我们扩展的时候$len(s,x)$与$len(y,t)$中的一项必然变小(否则你就没有扩展啊)
况2:
当前的最大值是$fmax$而反观我们的式子$max(fmax,len(s,x),len(x,t))$
当我们扩展的时候$len(s,x)$与$len(y,t)$中的两项不会由任何一项变大,所以最大值仍为$fmax$
综上:
当我们扩展这条链时,答案显然不会变得更劣
得证:)
于是我们就可以直接用两个指针在$O(n)$的时间复杂度内实现路径的枚举
代码
代码框架:
- 前向星
- DFS求直径
- 通过爬father的过程来找直径上的具体点
- 然后同时使用两个指针维护枚举路径
具体实现:
1 |
|
温馨提示:fmax为一个库函数名
例题:
就是一道题,也只有一道模板题
个人认为这个知识点很难考
因为这个知识点一旦需要套,那么就明显需要知道具体哪条路径
然而这样你就没法优化了啊(实际上优化2能用)