纪念一下过的第一道交互类型的题目。

题目Link

题意:$n$ 个点 $m$ 条边的无向图,$q$ 组询问 $(x,y)$ ,问从 $x,y$ 分别走到对方,让路径上边权的最大值最小,要求两条路径不完全重合。

各个子任务真的都多少指向了正解吧。。

$q\leq 5$ 的部分让我们想到了 $\mathcal O(qn\log n)$ 的二分答案

想这个 Subtask 的时候需要思考一些实现细节,比如简化一下题意,即二分出一个答案 $k$ ,我们利用 Kruskal 的思想,把边权小于等于 $k$ 的边都加进去,如果 $x,y$ 连通,那么说明这个 $k$ 允许我们有一条路径让 $x$ 到达 $y$ 。

问题是我们需要两条不完全重合的路径,于是 $m=n-1$(树)的部分是两点之间路径唯一,那我们只能让一个点走出这条路径一步,等另一边走到了终点再走过去。特殊的,如果从起点只有一条路退出去是不行的,否则另一边走到了自己的位置之后就走不回去了。

停下来观察一下,我们需要路径上任意一点的度数大于 $2$,这样即使是在初始 $x$ 就退一步到 $z_1$,$y$ 到达 $x$ 的位置之后,还有一个空位 $z_2$ 可以走过去停留,让 $x$ 走过去,路径上的点同理。

于是不难想到,要两条不完全重合的路径,我们只需要让这条路径上的点有一个度数超过2的,这样我们就可以走出这条链,等待另一边过去之后再继续走。这个用简单的权值并查集可以实现。

考虑整体二分,但是会发现题目这个实现的要求迫使强制在线,那么就想其他算法。

发现 Kruskal 的思路可以继续沿用,考虑 Kruskal 重构树。即做生成树时,如果一对 $(u,v)$ 成功连通两个连通块,那么改变原来把它们 merge 起来的做法,而是新建一个点 $f$,把 $u,v$ 都在并查集上并到 $f$ 上,然后在图上把 $get(u),get(v)$ 连向父亲 $f$。这样做完生成树之后,就得到了一棵 Kruskal 重构树。

并且在这道题中,我们把对应的权值 $w$ 作为点权赋值给父亲 $f$。这样的话如果只考虑一条路径的话,$x,y$ 之间的答案就是 $lca(x,y)$ 的点权。

因为当产生它们的 $lca$ 的边加进去之后它们才连通,而边权又是从小到大加入的,于是到 $lca$ 的点权就是最优的答案。

到这里已经很接近正解了。我们发现,$lca$ 及其之上的点都可以满足让 $x,y$ 连通,那么我们就从 $lca$ 向上找到其最近的一个点使其满足有路径点数大于2。发现这个性质是可以合并的,即挨着加边进去的时候让 $u,v$ 的度数加一,如果其中有大于2的,那么新合并出来的点就拥有这个性质。

于是我们就得到了某些点天然有这个性质,加完边之后 dfs 下去就可以传递最近的拥有性质的祖先结点了。

打出来发现会过不了样例,为什么呢?

考虑在加入边 $(u,v)$ 时它们已经连通,最简单的是形成了一个 $(a-b-c-a)$ 的环,图中每个点的度数都是2,但我们是可以让 $a,b$ 分别走到对方的位置的,这种情况特判一下就好了。

完整代码Link

最后修改:2021 年 09 月 03 日
如果觉得我的文章对你有用,请随意赞赏