本文共 4299 字，大约阅读时间需要 14 分钟。

$$【模板】静态仙人掌$$

题目链接：

题目背景

这是一道静态仙人掌 (Block Forest Data Structure) 的模板题。

任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。

题目

给你一个有 $n$ 个点和 $m$ 条边的仙人掌图，和 $q$ 组询问

输入

第一行三个正整数 $n,m,q$ ，意义如题目描述。

输出

$q$ 行，每行一个正整数，对应一次询问的结果。

样例输入1

9 10 21 2 11 4 13 4 12 3 13 7 17 8 27 9 21 5 31 6 45 6 11 95 7

样例输出1

56

样例解释

样例 $1$ 中的仙人掌是这个样子的：

样例输入2

9 10 31 2 12 3 12 4 43 4 24 5 15 6 16 7 27 8 28 9 45 9 21 95 83 4

样例输出2

752

数据范围

$1\le n,q\le 10000$

提示

请注意时限为 $300\text{ms}$

思路

这道题是一个叫做圆方树的东西。

假设图示这样的，那我们把原来的图里面的点叫做圆点，如果图中有环，就建一个方点连向环的各个点，原来的这个环的边就抹掉。就像这样：

1. lca 是圆点，就是普通的两点距离。
2. lca 是方点，就找到 lca 的儿子中分别是 $x$ 和 $y$ 的祖先的那两个点 $X,Y$ ，那答案就是两个儿子分别到他们祖先的距离之和再加上他们祖先的最短距离（因为两祖先在一个环内，两条路最短的那条就是了），就是答案。

要开 $longlong$ ，好像不用快读快输但是我用了。

代码

#include
   
    #include
    
     #include
     
      #define ll long longusing namespace std;struct node {   	ll x, to, nxt;}e[400001], ee[400001];ll n, m, q, x, y, z, w, ans;ll nn, KK, KKK, lca, X, Y;ll l[100001], fa[200001], dep[200001], dis[200001], diss[200001];ll dfn[200001], low[200001], le[200001], lee[200010], fath[21][200001];ll read() {   //快读	ll an = 0, zhengfu = 1;	char c = getchar();	while (c < '0' || c > '9') {   		if (c == '-') zhengfu = -zhengfu;		c = getchar();	}	while (c >= '0' && c <= '9') {   		an = an * 10 + c - '0';		c = getchar();	}	return an * zhengfu;}void add0(ll x, ll y, ll z) {   //建原图	e[++KK] = (node){   z, y, le[x]}; le[x] = KK;	e[++KK] = (node){   z, x, le[y]}; le[y] = KK;}void add(ll x, ll y, ll z) {   //建圆方树的图	ee[++KKK] = (node){   z, y, lee[x]}; lee[x] = KKK;	ee[++KKK] = (node){   z, x, lee[y]}; lee[y] = KKK;}void build(ll x, ll y, ll lon) {   //建方点	nn++;	ll len = lon;	for (ll i = y; i != fa[x]; i = fa[i]) {   		diss[i] = len;		len += l[i];	}	diss[nn] = diss[x];	diss[x] = 0;	for (ll i = y; i != fa[x]; i = fa[i]) {   		len = min(diss[i], diss[nn] - diss[i]);		add(i, nn, len);	}}void dfs1(ll now) {   //tarjan	dfn[now] = low[now] = ++w;	for (ll i = le[now]; i; i = e[i].nxt)		if (e[i].to != fa[now]) {   			if (!dfn[e[i].to]) {   				fa[e[i].to] = now;				l[e[i].to] = e[i].x;				dfs1(e[i].to);				low[now] = min(low[now], low[e[i].to]);			}			else low[now] = min(low[now], dfn[e[i].to]);			if (low[e[i].to] > dfn[now]) add(now, e[i].to, e[i].x);//圆点和圆点连边		}		for (ll i = le[now]; i; i = e[i].nxt)		if (fa[e[i].to] != now && dfn[now] < dfn[e[i].to])			build(now, e[i].to, e[i].x);//找到环建方点}void dfs2(ll now) {   //遍历来预处理	dep[now] = dep[fath[0][now]] + 1;	for (int i = 1; i <= 20; i++)		fath[i][now] = fath[i - 1][fath[i - 1][now]];	for (ll i = lee[now]; i; i = ee[i].nxt)		if (ee[i].to != fath[0][now]) {   			fath[0][ee[i].to] = now;			if (!dis[ee[i].to]) dis[ee[i].to] = dis[now] + ee[i].x;				else dis[ee[i].to] = min(dis[ee[i].to], dis[now] + ee[i].x);			dfs2(ee[i].to);		}}ll LCA(ll x, ll y) {   //求lca	if (dep[x] < dep[y]) swap(x, y);	for (ll i = 20; i >= 0; i--)		if (dep[fath[i][x]] >= dep[y])			x = fath[i][x];	for (ll i = 20; i >= 0; i--)		if (fath[i][x] != fath[i][y]) {   			x = fath[i][x];			y = fath[i][y];		}		X = x;	Y = y;	if (x == y) return x;	return fath[0][x];}void writec(ll x) {   //快输	if (x > 9) writec(x / 10);	putchar(x % 10 + '0');}void write(ll x) {   	if (x < 0) writec(-x);	writec(x);	putchar('\n');}int main() {   	n = read();//读入	m = read();	q = read();	nn = n;	for (ll i = 1; i <= m; i++) {   		x = read();//读入		y = read();		z = read();		add0(x, y, z);//建原来的图	}		dfs1(1);//建圆方树	fath[0][1] = 1;	dfs2(1);//初始化		for (ll i = 1; i <= q; i++) {   		x = read();//读入		y = read();		lca = LCA(x, y);//求出lca		if (lca > n) {   //lca在方点			ans = dis[x] - dis[X] + dis[y] - dis[Y];			ll far = abs(diss[X] - diss[Y]);			ans = ans + min(far, diss[lca] - far);		}		else ans = dis[x] - dis[lca] + dis[y] - dis[lca];//在圆点		write(ans);//输出	}		return 0;}