RainAir
My OI Blog
RainAir
「CF487E」Tourists

题目链接

题目描述

给定 $n$ 个点 $m$ 条边的连通点权无向图。
有 $q$ 个操作,要么修改一个点的点权,要么询问两点间经过一条从 $s$ 到 $t$ 的简单路径,路径上最小点权最小值是多少。
$ n,m,q \leq 10^5 $.

题解

问的是所有可能路径上的最小点权的最小值,那我们来考虑一下路径的性质。
首先我们可以发现,如果将这个图分成几个点双联通分量的话,路径一定是经过了从 $s$ 到 $t$ 的点双连通分量,而在每一个点双里是可以随便选择一个点经过的。所以这个问题就变成了:求经过的点双的点权最小值的最小值。
我们考虑建出圆方树,考虑方点维护该边双内圆点权值的最小值,每次修改的时候暴力修改该圆点所连接的方点记录的信息,然后就变成查询树上路径点权最小值了,可以使用树链剖分求解。
但是注意到如果我们构造一张菊花图,那么每次对于圆点的修改就退化为 $O(n)$ 了,不能接受。
不如我们改变方点维护的东西:我们维护除了父亲圆点的圆点点权最小值,查询的时候额外考虑方点父亲对答案的影响就好了。可以使用 multiset 维护。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/422
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「CF487E」Tourists
题目链接 题目描述 给定 $n$ 个点 $m$ 条边的连通点权无向图。 有 $q$ 个操作,要么修改一个点的点权,要么询问两点间经过一条从 $s$ 到 $t$ 的简单路径,路径上最小点权最小值是多少。…
扫描二维码继续阅读
2019-01-23
标签
近期评论