CF1632E2 题解

GaryH · 2022-02-03 17:07:07 · 题解

CF1632E1&E2 题解

题意：

给一棵初始边权为 1 的树，对于所有 x\in[1,n]，求：

若能添一条权为 x 的无向边 (a,b)，则 \max\limits_{i=1}^n(d_i) 的最小值是多少，

其中 d_i 等于 点 1 到点 i 的最短路径的长度。

做法：

先考虑对于固定 x 后如何计算答案。

首先，问题可以转化为，我们添加的边至少有一个端点是 1。

因为，对于一张加了边 u\leftrightarrow v(u,v>1) 的新图 A，此处我们假设 d_u\leq d_v，

则加了边 1\leftrightarrow v 的新图 B 一定更优。我们通过枚举 A 中的决策来证明：

任意一条 A 中的路径 p=1\rightarrow\cdots\rightarrow t，

若 p 中不包含新边 u\leftrightarrow v，则 B 方式中也存在路径 q=p；

而若 p 中包含新边 u\leftrightarrow v，即 p=1\rightarrow\cdots\rightarrow u\rightarrow v \rightarrow s\rightarrow\cdots\rightarrow t，

我们能在 B 方式中找到路径 q=1\rightarrow v \rightarrow s\rightarrow\cdots \rightarrow t，

其中 q 中经过了新边 1\rightarrow v，且 q 的长度必然不大于 p 的长度。

那么我们考虑新问题的做法，这时我们考虑二分答案，那么问题就又转化为：

对于值 ans，是否存在一点 v，使得加入边 1\leftrightarrow v 后的新图 G 的 \max\limits_{i=1}^n(d_i) 的最小值不大于 ans。

那么，原树里 d_u>ans 的点 u 都必须被新边 1\leftrightarrow v 影响而使得 d'_u\le ans，

其中 d'_u 是加边后点 1 到点 u 的距离。

再考虑新家的边是如何影响 d 数组的变化的，即加入权为 x 的新边 1\leftrightarrow v 后，我们有：