Codeforces 1046B

题意

给你一张 $n$ 个点 $m$ 条边的无向图，满足每一个简单环上的点两两有边

$q$ 次询问两个点之间的最短路

$n\le 10^5,m\le510^5,q\le210^5$

Codeforces 487E

题意

给你一张 $n$ 个点 $m$ 条边的无向图，每个点有点权，$q$ 次操作

1. C a w，将第 $a$ 个点的权值改为 $w$

2. A a b，询问 $a$ 到 $b$ 所有可能的简单路径上的点权最小值

简单路径即不经过一个点超过一次的路径

$n,m,q\le 10^5$

LOJ #2587

题意

你有一张 $n$ 个点 $m$ 条边的无向图，你需要选择三个互不相同的点 $s,c,f$

询问有多少种选择的方案使得存在至少一条从 $s$ 出发经过 $c$ 到达 $f$ 的简单路径（不经过重复点）

$n\le 10^5,m\le 2*10^5$

BZOJ 1023

题意

你有一棵$n$个点的仙人掌，边权为$1$

定义两点的距离是最短路的长度

定义仙人掌的直径是距离最远的两点的距离

求直径

$n\le5*10^4$

BZOJ 4316

题意

你有一棵边仙人掌，求最大点独立集

$n\le510^4,m\le610^4$

BZOJ 2125

题意

给定 $n$个 点仙人掌（每条边只在不超过1个简单环中的无向连通图），$q$ 次询问两点间最短路

边带权

$n,q\le 10000$