「CF487E」Tourists
题目链接题目描述给定 $n$ 个点 $m$ 条边的连通点权无向图。 有 $q$ 个操作，要么修改一个点的点权，要么询问两点间经过一条从 $s$ 到 $t$ 的简单路径，路径上最小点权最小值是多少。 $ n,m,q \leq 10^5 $.题解问的是所有可能路径上的最小点权的最小值，那我们来考虑一下路径的性质。 首先我们可以发现，如果将这个图分成几个点双联通分量的话，路径一定是经过了从 $s$...
题目链接题目描述给定 $n$ 个点 $m$ 条边的连通点权无向图。 有 $q$ 个操作，要么修改一个点的点权，要么询问两点间经过一条从 $s$ 到 $t$ 的简单路径，路径上最小点权最小值是多少。 $ n,m,q \leq 10^5 $.题解问的是所有可能路径上的最小点权的最小值，那我们来考虑一下路径的性质。 首先我们可以发现，如果将这个图分成几个点双联通分量的话，路径一定是经过了从 $s$...
点双连通分量点双连通图：如果一个无向图上没有割点，那么该图为点双连通图。显然有一个性质是同一个点双连通图中任意两点至少存在两条不经过重复点的路径。 点双连通分量：一个无向图的极大点双连通子图 我们可以使用 Tarjan 求解。 大家肯定都会无向图求割点了，我们其实只需要稍微改一下就可以了。 我们可以发现割点是两个点双的分割点，所以我们用栈来保存按照 $dfn$ 排序的目前还能进入新的点双里的...