[Codeforces Round #334(Div.1)] 603E-Pastoral Oddities

一道很棒的分治题

题目页面(603E)

这个题做法目前来看有三种:

1.LCT维护最小生成树;

2.cdq分治(或整体二分);

3.线段树分治

实际上第2种方法是最好写的……不过就是跑的有点慢(应该是我的写法问题)。

那接下来就介绍一下第二种写法吧(


首先可以发现,一个连通块是满足条件的,当且仅当连通块的点数为偶数。

也就是说,连通块的点数为奇数时就不行。由此可见,当 $n\bmod 2==1$ 时答案全都为 $-1$。

然后这个题要求所有合法连通块中最大的边(这题非要把 edge 说成 path,导致我一开始以为是要求最长最短路最短禁止套娃)。所以不难想到,我们所需要的边一定在这个连通块的最小生成树上。

我们首先将所有的边按照权值从小到大排序,像Kruskal那样。

考虑分治:我们令 $solve(l,r,low,up)$ 表示当前处理的区间为 $[l,r]$,答案的区间为 $[low,up]$。接下来,就考虑怎么统计答案。

考虑Kruskal算法:我们需要用并查集来维护这棵树,这道题我们也可以用相同的方法,不过由于会带有删边操作(将 $x$ 到其父亲 $fx$ 这条边删掉),那么我们的并查集也就得支持撤销操作,所以不能写路径压缩。为了优化,我们可以将按秩合并优化放上去,即将小树接到大树的根上,这样均摊下来复杂度不会太高。

然后就是分治过程:每一次我们计算 $mid=(l+r)>>1$ 的答案。由于我们当前要计算的答案区间为 $[low,up]$,那么 $[l,mid]$ 的这些边中,可能会有一些边的权值小于等于 $low$。可以发现:对于一个连通块,连的边越多越好(连通块合法的前提下)。那么我们就将这些边加上去,对应的点就用并查集搞起来。之后,我们再将权值在 $[low,up]$ 中的边从小到大依次加进去,用 $cnt$ 记录不合法的连通块数量($cnt$ 一开始为 $n$),那么加完边或者加到中间 $cnt=0$ 的话说明当前存在一个合法方案,答案就是最后加的那条边的权值。

然后就是cdq分治或者整体二分的套路了:我们将并查集过程中更新过的这些根用一个栈存起来,每一次统计完就将这些点与其父亲相连的边删掉即可,否则会重复统计答案。

代码中 $low$ 和 $up$ 并没有直接代表权值,而是相当于将权值离散化一下得到的权值下标之类的东西。这样可以优化一点常数。

……不过仍然比较慢就是了。

 

发表评论