标签：DIAMETER le dist max 端点直径 operatorname

直径 [zhí jìng]

捷速，直接。

汉司马相如《大人赋》：“西望崑崙之轧沕荒忽兮，直径驰乎三危。”

连接圆周上两点并通过圆心的直线称圆直径，连接球面上两点并通过球心的直线称球直径。

宋沈括《梦溪笔谈·技艺》：“以圆径除所得，加入直径，为割田之弧。”

刘宾雁《一个人和他的影子》：“这是一个两吨容量的锅炉，胴体直径一米四。”

没有人喜欢做几何题，那么显然 OI 里我们取的是第一个意思。

求直径

这个比较简单，但是还是写一下吧。~~这样以后写直径就可以复制这里的板子不用查以前代码了~~

主要有两种方法，都是 \(\operatorname{O}(n)\)的，比较快。~~符合捷速，直接的定义~~

一种是两次 dfs，思路不再赘述。可以求出具体路径，但是当存在负边权时无法使用。
另外一种是树形 dp，可以解决负边权，但是不太好求路径。有两种写法。

代码在这里

~~以下才是正题~~

记号规定

\(dist(u,v)\) 表示 \(u\)，\(v\) 两点间的距离。
\(P(u,v)\) 表示 \(u\) 到 \(v\) 的边或路径。

直径的性质

对于直径，有一个美妙的性质，姑且称为最长性。这是说，对于一条直径，设端点为 \(u\)，\(v\)，现有直径上一点 \(p\)，和一条从 \(u\)，\(p\) 之间分支出去的路径，假设到达的叶子结点为 \(q\)，一定有 \(dist(q,p)\le dist(u,p)\)。证明显然，若 \(q\) 到 \(p\) 的距离更大，\(u\) 就不是直径的端点，而应该是 \(q\)。
由此可以推出以下几个：
- 所有直径必交于一点。这一点是一个节点，也可能在某条边上。
- 对于树上任意一点，能到达的最远点一定是直径端点之一。
- \(\dots\)

[SDOI2013] 直径

求直径和直径的必须边。

求得直径之后，我们可以求出直径上每个点在不经过直径的情况下所能到达的最大距离，记为 \(d\)。
从直径的中心开始，向两边枚举。（以端点 \(u\) 这一侧为例，枚举到 \(p\) 点）比较 \(d(p)\) 和 \(dist(u,p)\)。若相等，说明可以用 \(d(p)\) 对应的路径替换 \(P(u,p)\)，则剩余的边都不是必须边，直接 break。否则（即 \(d(p)<dist(u,p)\)，根据最长性不可能大于）枚举下一个点 \(p'\)，并且 \(P(p,p')\) 为必须边。
只看一侧的原因是 \(p\) 不可能对 \(v\) 做出贡献。假设可能，即 \(d(p)=dist(p,v)\)，又可知 \(dist(u,p)<dist(p,v)\)，所以 \(dist(u,p)<d(p)\)。显然不成立，所以只用考虑一侧。
但是中心可能在边上，需要判断一下。

时间复杂度 \(\operatorname{O}(n)\)。

代码写的比较繁琐）））

[NOIP2007 提高组] 树网的核

这题很厉害。题意太长就不写了/kk。

solution 1

首先看到 \(n\le 300\)，直接暴力。求完直径，枚举 \(F\) 的两个端点，再深搜求最远距离，\(\operatorname{O}(n^3)\)。没有然后了，这样就过了。

不过注意到路径 \(F\) 变长并不会让答案变劣，所以枚举一个端点，就可以确定另一个端点，\(\operatorname{O}(n^2)\)。~~并没有什么用~~

这数据太水了吧，你告诉我这是提高组？所以我们有了加强版（点这里）。

solution 2

\(n\le 5\times 10^5\)，不能暴力了（悲）

最小偏心距，你不想二分吗？

我们二分一个 \(mid\)，问题转换成了判定是否存在一个 \(F\) 使得最小偏心距为 \(mid\)。按照正常的求法，偏心距分为了两部分，一部分是 \(F\) 的端点到直径端点的距离，另一部分是 \(F\) 上的点到非直径的点的最远距离。现在分开考虑。

设直径为 \(P(u,v)\)，现在找到一个直径上的点 \(p\)，使得 \(dist(u,p)\) 在不超过 \(mid\) 的情况下最大；\(v\) 同理，找到的点记为 \(q\)。
根据直径的性质，可知 \(p\) 到任何非直径点的距离都不超过 \(dist(u,p)\)，即不超过 \(mid\)；\(q\) 同理。那么只需检查 \(dist(p,q)\) 是否不超过 \(s\) 以及 \(P(p,q)\) 上的点的 \(d\) 数组是否不超过 \(mid\) 即可（\(d\) 的定义同上题）。

为什么 \(P(u,p)\) 和 \(P(q,v)\) 一定要取极限情况？不取可以吗？会漏掉情况吗？不取当然可以，但是取了也不会漏掉情况。假如我不取最远的点 \(p\)，取离 \(u\) 更近的 \(p'\)，则：

由取 \(p\) 的情况可知，\(\forall i\;on\;P(u,p),d(i)\le mid\)，所以 \(p\) 与 \(p'\) 其实都满足情况，是等价的。取极限情况只是为了让程序少跑几个点，更快一点。

时间复杂度 \(\operatorname{O}(n\log \sum w)\)

solution 3

当然了，我们还有更快的方法。

若直径上的点集 \(V=\{u_1,u_2,u_3,\dots,u_t\}\)，

则对于每一个可能的 \(F'=P(u_i,u_j)\) 的偏心距，都有：

\[Ans=\max(\max\limits_{i\le k\le j}{d(u_k)},dist(u_1,u_i),dist(u_j,u_t)) \]

对于括号里的三项来说，后两项可以 \(\operatorname{O}(1)\) 计算，第一项完全可以使用单调队列计算。

但是我不会写单调队列怎么办？

根据直径的最长性，可得：

\[Ans=\max(\max\limits_{i\le k\le j}{d(u_k)},dist(u_1,u_i),dist(u_j,u_t)) \]

\[\ \ \ \ \ \ \ \ \ =\max(\max\limits_{1\le k\le t}{d(u_k)},dist(u_1,u_i),dist(u_j,u_t)) \]

\(\max\limits_{1\le k\le t}{d(u_k)}\) 是定值，双指针维护后面的就好了。

最终我们达到了 \(\operatorname{O}(n)\)！

两部分代码在一起

[SDOI2011] 消防

这个题可以说是树网的核的再升级版，不仅数据范围变大了，还少了路径一定在直径上这个条件。

实际上我们要找的路径就是在直径上，所以代码和加强版是完全一样的。接下来考虑证明答案路径一定在直径上这个结论。

因为距离树上任意一点最远的点一定是直径的端点，所以把一个点从直径外挪到直径上答案一定不会变劣，所以路径一定会在直径上。

[APIO2010] 巡逻

首先看 \(k=1\) 的情况。

原本一棵树的情况下，每条边都需要走两次。现在又新加了一条边，也就是形成了一个环。显而易见环上的边只用走一次了。所以找到直径，这样可以减少最多的路程。

那 \(k=2\) 怎么办呢？

首先第一条边应该连直径，这个待会再说。

连了直径之后第二条边该怎么找呢？

我们需要再找一条链，使得它和直径的边集的权值和最大。不妨把直径上的边长都设为 \(-1\)，然后再求直径，就得到了我们要求的链。

因为是求直径，所以会尽量走大的边，尽量少走 \(-1\) 的边。而我们确实应该少走 \(-1\) 的边：它已经走过了。如果两条链有相交，那么相交的部分一定会经过两次（不然新边无法正好通过一次），所以我们要尽量减少相交。

一共 \(n\) 个点，两次直径分别为 \(L_1,L_2\)，则：

\[Ans=2\times(n-1)-(L_1-1)-(L_2-1)=2\times n-L_1-L_2 \]

那么凭什么上来先求直径呢？

理性证明十分困难，我也不会，只能感性理解一下了：

我们要做是找到两条边权和最大的路径，类比网络流，我们做两次增广，但是要找到最长的，所以第一次找直径；接着将直径取反，相当于构建了残量网络，所以再找最大的还是直径。

代码最好写的一集，就不用放了。

Luogu P2195 HXY造公园

~~双倍经验~~

简单来说给了我们一个森林，每次把两棵树拼接在一起，要求拼接后的新树直径最小。

最初的直径可以直接求出。现在考虑连接 \(P(u,v)\)：

新的直径有三个来源：

\(u\) 所在联通块的直径（\(L_u\)），
\(v\) 所在联通块的直径（\(L_v\)），
跨越 \(P(u,v)\) 的直径。

~~话说是不是本质上就两个？~~前两个我们已经提前求出了。对于第三个，因为本题边权都为 \(1\)，所以十分好办，即：

\[\lceil\frac{L_u}{2}\rceil+\lceil\frac{L_v}{2}\rceil+dist(u,v) \]

那么

\[L_{new}=\max(L_u,L_v,\lceil\frac{L_u}{2}\rceil+\lceil\frac{L_v}{2}\rceil+dist(u,v)) \]

前两个自不必说。第三个本质上是求了两个“半径”加起来。“半径”其实就是以一个点为起点，所能达到的最远距离，我们记为 \(R\)。而要想让 \(u\) 能到达的最远距离最短，我们根据直径的性质，直接把 \(u\) 放到直径的中点，这样一定最短。接着把 \(R(u)\) 和 \(R(v)\) 拼起来，就得到了上式。

代码最好写的第二集，实在太好写了，还是不贴。

[TJOI2017] 城市

这道题和上道题十分地类似，我愿称之为升级版。

给定一棵树，要求删去一条边，加上一条边权相同的边，在保持树形态的前提下直径最小。

solution

比较友好的一点在于 \(n\le 5000\)，在 \(3\) 秒的时限下 \(\operatorname{O}(n^2)\) 是能过的。

还是分成三种情况，算了，两种情况来讨论

\(u,v\) 所在联通块原本的直径，
跨越 \(P(u,v)\) 的新直径。

与上个题不同的是，因为是从原树上断边，所以没法提前求出 \(1\)，这时候就要启动树形 dp 了：

设 \(d_1(u),d_2(u),f(u)\)，分别表示从点 \(u\) 向下走能到达的最远、次远距离，以及从 \(u\) 的祖先到 \(u\) 的最远距离。

如果在 \(\operatorname{O}(n)\) 的时间内求出这三个数组，我们就可以得到答案：

\(1\) 即为：

\[Ans_1=\max\limits_{1\le u\le n}d_1(u)+d_2(u) \]

对 \(2\) 来说，我们还是先求出所谓半径，这是一个套路的换根 dp：

\[\begin{aligned} g(u)&=\begin{cases}d_1(fa_u)+dist(fa_u,u)\ \ \ \ \ \ \ \ [d_1(u)+dist(fa_u,u)\neq d_1(fa_u)],\\d_2(fa_u)+dist(fa_u,u)\ \ \ \ \ \ \ \ \operatorname{otherwise}\end{cases}\\\ \\\ f(u)&=\max(f(fa_u),g(u))+dist(fa_u,u) \\\ \\\ R(u)&=\max(d_1(u),f(u)) \\\ \\\ Ans_2&=\min\{R(u)\}+\min\{R(v)\}+dist(u,v) \end{aligned} \]

最后：

\[FinalAns=\min\limits_{P(u,v)\in E}\{\max(Ans_1,Ans_2)\} \]

\(E\) 是边集。

tips：写代码时将删去的边打上标记就不怕访问错啦。

代码在这里，但是我写的常数好像巨大，不吸氧不足以通过。理论上来说写好看点应该是可以的。

~~我不会告诉你我数组开小了调了一小时~~

more optimizations

但是在 AcWing 的 \(1\) 秒时限下即使吸氧也过不了。我们需要优化。

opti 1

依据上一题，直接找直径中点呗，我写了，比较难写。复杂度不会算，但是快了，不吸氧洛谷可过。

opti 2

实际上删去直径以外的边完全没有用，因为两个联通块里总是包含了原来的直径。所以只需枚举直径上的边就好了，\(\operatorname{O}(nL)\)，其中 \(L\) 是直径的边数。我懒，没写，据说优化很显著。

opti 3

我在学，学完再写/fendou

标签：DIAMETER,le,dist,max,端点,直径,operatorname
From： https://www.cnblogs.com/LHLeisus/p/18000131/diameter

DIAMETER