CCF GESP 2025年9月认证 C++ 8级
题目描述
给定正整数 $p,q$ 以及常数 $N=10^{18}$。现在构建一张包含 $N$ 个结点的带权无向图，结点依次以 $1,2,\ldots,N$ 编号。对于任意满足 $1\le u<v\le N$ 的 $u,v$，向图中加入一条连接结点 $u$ 与结点 $v$ 的无向边，边权取决于 $u,v$ 是否互质：
- 若 $u,v$ 互质（即 $u,v$ 的最大公因数为 $1$），则连接结点 $u$ 与结点 $v$ 的无向边长度为 $p$；
- 否则连接结点 $u$ 与结点 $v$ 的无向边长度为 $q$。
现在给定 $n$ 组询问，第 $i$（$1\le i\le n$）组询问给定两个正整数 $a_i,b_i$，你需要回答结点 $a_i$ 与结点 $b_i$ 之间的最短距离。
输入格式
第一行，三个正整数 $n,p,q$，分别表示询问数量，结点编号互质时的边权，以及结点编号不互质时的边权。
接下来 $n$ 行，每行两个正整数 $a_i,b_i$，表示一组询问。
输出格式
输出共 $n$ 行，每行一个整数，表示结点 $a_i$ 与结点 $b_i$ 之间的最短距离。
样例说明
样例 1
4 4 3
1 2
2 3
4 2
3 54
4
3
4样例 2
5 2 6
1 2
2 3
4 2
3 5
6 62
2
4
2
0数据范围
对于 $30\%$ 的测试点，保证 $1\le n\le 10$，$1\le a_i,b_i\le 50$。
对于另外 $30\%$ 的测试点，保证 $1\le a_i,b_i\le 250$。
对于所有测试点，保证 $1\le n\le 10^4$，$1\le a_i,b_i\le 10^9$，$1\le p,q\le 10^9$。
题目描述
给定一张包含 $n$ 个结点 $m$ 条边的带权连通无向图，结点依次以 $1,2,\ldots,n$ 编号，第 $i$ 条边（$1\le i\le m$）连接结点 $u_i$ 与结点 $v_i$，边权为 $w_i$。
对于每条边，请你求出从图中移除该条边后，图的最小生成树中所有边的边权和。特别地，若移除某条边后图的最小生成树不存在，则输出 $-1$。
输入格式
第一行，两个正整数 $n,m$，分别表示图的结点数与边数。
接下来 $m$ 行中的第 $i$ 行（$1\le i\le m$）包含三个正整数 $u_i,v_i,w_i$，表示图中连接结点 $u_i$ 与结点 $v_i$ 的边，边权为 $w_i$。
输出格式
输出共 $m$ 行，第 $i$ 行（$1\le i\le m$）包含一个整数，表示移除第 $i$ 条边后，图的最小生成树中所有边的边权和。若移除第 $i$ 条边后图的最小生成树不存在，则输出 $−1$。
样例说明
样例 1
5 5
1 2 4
2 3 3
3 4 1
2 5 2
3 1 814
15
-1
-1
10样例 2
6 10
1 2 6
2 3 3
3 1 4
3 4 5
4 5 8
5 6 2
6 4 1
3 2 4
5 4 4
3 3 615
16
17
-1
15
17
18
15
15
15数据范围
对于所有测试点，保证 $1\le n\le 10^5$，$1\le m\le 10^5$，$1\le u_i,v_i\le n$，$1\le w_i\le 10^9$。