RainAir
My OI Blog
RainAir

圆方树
文章归档

「CF487E」Tourists

题目链接 题目描述 给定 $n$ 个点 $m$ 条边的连通点权无向图。 有 $q$ 个操作,要么修改一个点的点权,要么询问两点间经过一条从 $s$ 到 $t$ 的简单路径,路径上最小点权最小值是多少。 $ n,m,q \leq 10^5 $. 题解 问的是所有可能路径上的最小点权的最小值,那我们…

   356   2019-01-23 去围观

点双连通分量 & 圆方树学习笔记

点双连通分量 点双连通图:如果一个无向图上没有割点,那么该图为点双连通图。显然有一个性质是同一个点双连通图中任意两点至少存在两条不经过重复点的路径。 点双连通分量:一个无向图的极大点双连通子图 我们可以使用 Tarjan 求解。 大家肯定都会无向图求割点了,我…

   816   2019-01-21 去围观
标签
近期评论