Codeforces 1046B

题意

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

\(q\) 次询问两个点之间的最短路

\(n\le 10^5,m\le5*10^5,q\le2*10^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\le5*10^4,m\le6*10^4\)

BZOJ 2125

题意

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

边带权

\(n,q\le 10000\)