0x60图论（0x64 基环树）例题3：Freda的传呼机

数据byscy20231101

P5236 【模板】静态仙人掌

题目背景

这是一道静态仙人掌(Block Forest Data Structure)的模板题。
如果您不知道什么是仙人掌，那么此处给出无向仙人掌图的定义：

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

题目描述

给你一个有 $n$ 个点和 $m$ 条边的仙人掌图，和 $q$ 组询问
每次询问两个点 $u,v$，求两点之间的最短路。

保证输入数据没有重边。

输入格式

第一行三个正整数 $n,m,q$，意义如题目描述。
接下来 $m$ 行，每行三个正整数 $u,v,w$，表示 $u,v$ 之间有一条权值为 $w$ 的无向边。
然后 $q$ 行，每行两个正整数 $u,v$，询问 $u$ 到 $v$ 的最短路。

输出格式

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

输入输出样例 #1

输入 #1

9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7

输出 #1

5
6

输入输出样例 #2

输入 #2

9 10 3
1 2 1
2 3 1
2 4 4
3 4 2
4 5 1
5 6 1
6 7 2
7 8 2
8 9 4
5 9 2
1 9
5 8
3 4

输出 #2

7
5
2

说明/提示

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

询问有两个，分别是询问 $1\rightarrow 9$ 和 $5\rightarrow 7$ 的最短路
显然答案分别为 $5$ 和 $6$。

数据范围：
$1\le n,q \le 200000$
$1\le m \le 300000$
$1\le w \le 10^5$

保证输入数据没有重边。

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