ACGO 上仍然没有在主题库中发出 GESP 202509 的真题，于是我开始帮助 AC 君了。 @AC君 加个精吧.
题解的话，我有空发在另外一个帖子上
一级：
[GESP202509 一级] 金字塔
题目描述
金字塔由 nnn 层石块垒成。从塔底向上，每层依次需要 n×n,(n−1)×(n−1),⋯ ,2×2,1×1n \times n, (n-1) \times (n-1), \cdots, 2 \times 2, 1 \times 1n×n,(n−1)×(n−1),⋯,2×2,1×1 块石块。请问搭建金字塔总共需要多少块石块？
输入格式
一行，一个正整数 nnn，表示金字塔的层数。
输出格式
一行，一个正整数，表示搭建金字塔所需的石块数量。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
对于所有测试点，保证 1≤n≤501 \leq n \leq 501≤n≤50。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
[GESP202509 一级] 商店折扣
题目描述
商店正在开展促销活动，给出了两种方案的折扣优惠。第一种方案是购物满 xxx 元减 yyy 元；第二种方案是直接打 nnn 折，也就是说价格变为原先的 n/10n/10n/10。这里的 x,y,nx, y, nx,y,n 均是正整数，并且 1≤y<x1 \leq y < x1≤y<x，1≤n<101 \leq n < 101≤n<10。
需要注意的是，第一种方案中满减优惠只能使用一次。例如购物满 101010 元减 333 元时，若挑选了价格总和为 333333 元的物品，只能减免 333 元，需要支付 303030 元。
小明在商店挑选了价格总和为 ppp 元的物品，结账时只能使用一种优惠方案。小明最少需要支付多少钱呢？
输入格式
四行，四个正整数 x,y,n,px, y, n, px,y,n,p，含义见题目描述。
输出格式
一行，一个小数，表示小明最少需要支付多少钱，保留两位小数。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
对于所有测试点，保证 1≤y<x≤1001 \leq y < x \leq 1001≤y<x≤100，1≤n<101 \leq n < 101≤n<10，1≤p≤1001 \leq p \leq 1001≤p≤100。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二级：
[GESP202509 二级] 优美的数字
题目描述
如果一个正整数在十进制下的所有数位都相同，小 A 就会觉得这个正整数很优美。例如，正整数 666 的数位都是 666，所以 666 是优美的。正整数 999999 的数位都是 999，所以 999999 是优美的。正整数 123123123 的数位不都相同，所以 123123123 并不优美。
小 A 想知道不超过 nnn 的正整数中有多少优美的数字。你能帮他数一数吗？
输入格式
一行，一个正整数 nnn。
输出格式
一行，一个正整数，表示不超过 nnn 的优美正整数的数量。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
对于所有测试点，保证 1≤n≤20251 \leq n \leq 20251≤n≤2025。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
[GESP202509 二级] 菱形
题目描述
小 A 想绘制一个菱形。具体来说，需要绘制的菱形是一个 nnn 行 nnn 列的字符画，nnn 是一个大于 111 的奇数。菱形的四个顶点依次位于第 111 行、第 111 列、第 nnn 行、第 nnn 列的正中间，使用 # 绘制。相邻顶点之间也用 # 连接。其余位置都是 .。
例如，一个 555 行 555 列的菱形字符画是这样的：
给定 nnn，请你帮小 A 绘制对应的菱形。
输入格式
一行，一个正整数 nnn。
输出格式
输出共 nnn 行，表示对应的菱形。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
对于所有测试点，保证 3≤n≤293 \leq n \leq 293≤n≤29 并且 nnn 为奇数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三级：
[GESP202509 三级] 日历制作
题目描述
小 A 想制作 202520252025 年每个月的日历。他希望你能编写一个程序，按照格式输出给定月份的日历。
具体来说，第一行需要输出 MON TUE WED THU FRI SAT SUN，分别表示星期一到星期日。接下来若干行中依次输出这个月所包含的日期，日期的个位需要和对应星期几的缩写最后一个字母对齐。例如，202520252025 年 999 月 111 日是星期一，在输出九月的日历时，111 号的个位 111 就需要与星期一 MON 的最后一个字母 N 对齐。九月的日历输出效果如下:
你能帮助小 A 完成日历的制作吗?
输入格式
一行，一个正整数 mmm，表示需要按照格式输出 202520252025 年 mmm 月的日历。
输出格式
输出包含若干行，表示 202520252025 年 mmm 月的日历。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
对于所有测试点，保证 1≤m≤121 \leq m \leq 121≤m≤12。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
[GESP202509 三级] 数组清零
题目描述
小 A 有一个由 nnn 个非负整数构成的数组 a=[a1,a2,…,an]a = [a_1, a_2, \ldots, a_n]a=[a1 ,a2 ,…,an ]。他会对阵组 aaa 重复进行以下操作，直到数组 aaa 只包含 0。在一次操作中，小 A 会依次完成以下三个步骤：
1. 在数组 aaa 中找到最大的整数，记其下标为 kkk。如果有多个最大值，那么选择其中下标最大的。
2. 从数组 aaa 所有不为零的整数中找到最小的整数 aja_jaj 。
3. 将第一步找出的 aka_kak 减去 aja_jaj 。
例如，数组 a=[2,3,4]a = [2, 3, 4]a=[2,3,4] 需要 7 次操作变成 [0,0,0][0, 0, 0][0,0,0]：
[2,3,4]→[2,3,2]→[2,1,2]→[2,1,1]→[1,1,1]→[1,1,0]→[1,0,0]→[0,0,0][2, 3, 4] \rightarrow [2, 3, 2] \rightarrow [2, 1, 2] \rightarrow [2, 1, 1] \rightarrow [1, 1, 1] \rightarrow [1, 1, 0] \rightarrow [1, 0, 0] \rightarrow [0, 0, 0] [2,3,4]→[2,3,2]→[2,1,2]→[2,1,1]→[1,1,1]→[1,1,0]→[1,0,0]→[0,0,0]
小 A 想知道，对于给定的数组 aaa，需要多少次操作才能使得 aaa 中的整数全部变成 0。可以证明，aaa 中整数必然可以在有限次操作后全部变成 0。你能帮他计算出答案吗？
输入格式
第一行，一个正整数 nnn，表示数组 aaa 的长度。
第二行，nnn 个非负整数 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an ，表示数组 aaa 中的整数。
输出格式
一行，一个正整数，表示 aaa 中整数全部变成 0 所需要的操作次数。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
对于所有测试点，保证 1≤n≤1001 \leq n \leq 1001≤n≤100，0≤ai≤1000 \leq a_i \leq 1000≤ai ≤100。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四级：
[GESP202509 四级] 排兵布阵
题目描述
作为将军，你自然需要合理地排兵布阵。地图可以视为 nnn 行 mmm 列的网格，适合排兵的网格以 1 标注，不适合排兵的网格以 0 标注。现在你需要在地图上选择一个矩形区域排兵，这个矩形区域内不能包含不适合排兵的网格。请问可选择的矩形区域最多能包含多少网格？
输入格式
第一行，两个正整数 n,mn, mn,m，分别表示地图网格的行数与列数。
接下来 nnn 行，每行 mmm 个整数 ai,1,ai,2,…,ai,ma_{i,1}, a_{i,2}, \ldots, a_{i,m}ai,1 ,ai,2 ,…,ai,m ，表示各行中的网格是否适合排兵。
输出格式
一行，一个整数，表示适合排兵的矩形区域包含的最大网格数。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
对于所有测试点，保证 1≤n,m≤121 \leq n, m \leq 121≤n,m≤12，0≤ai,j≤10 \leq a_{i,j} \leq 10≤ai,j ≤1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
[GESP202509 四级] 最长连续段
题目描述
对于 kkk 个整数构成的数组 [b1,b2,…,bk][b_1, b_2, \ldots, b_k][b1 ,b2 ,…,bk ]，如果对 1≤i<k1 \leq i < k1≤i<k 都有 bi+1=bi+1b_{i+1} = b_i + 1bi+1 =bi +1，那么称数组 bbb 是一个连续段。
给定由 nnn 个整数构成的数组 [a1,a2,…,an][a_1, a_2, \ldots, a_n][a1 ,a2 ,…,an ]，你可以任意重排数组 aaa 中元素顺序。请问在重排顺序之后，aaa 所有是连续段的子数组中，最长的子数组长度是多少？
例如，对于数组 [1,0,2,4][1, 0, 2, 4][1,0,2,4]，可以将其重排为 [4,0,1,2][4, 0, 1, 2][4,0,1,2]，有以下 101010 个子数组：
[4],[0],[1],[2],[4,0],[0,1],[1,2],[4,0,1],[0,1,2],[4,0,1,2][4], [0], [1], [2], [4, 0], [0, 1], [1, 2], [4, 0, 1], [0, 1, 2], [4, 0, 1, 2] [4],[0],[1],[2],[4,0],[0,1],[1,2],[4,0,1],[0,1,2],[4,0,1,2]
其中除 [4,0],[4,0,1],[4,0,1,2][4, 0], [4, 0, 1], [4, 0, 1, 2][4,0],[4,0,1],[4,0,1,2] 以外的子数组均是连续段，因此是连续段的子数组中，最长子数组长度为 3。
输入格式
第一行，一个正整数 nnn，表示数组长度。
第二行，nnn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an ，表示数组中的整数。
输出格式
一行，一个整数，表示数组 aaa 重排顺序后，所有是连续段的子数组的最长长度。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
对于 40%40\%40% 的测试点，保证 1≤n≤81 \leq n \leq 81≤n≤8。
对于所有测试点，保证 1≤n≤1051 \leq n \leq 10^51≤n≤105，−109≤ai≤109-10^9 \leq a_i \leq 10^9−109≤ai ≤109。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五级：
[GESP202509 五级] 有趣的数字和
题目背景
为保证只有时间复杂度合理的算法通过本题，本题时限下调。
题目描述
如果一个正整数的二进制表示包含奇数个 111，那么小 A 就会认为这个正整数是有趣的。
例如，777 的二进制表示为 (111)2(111)_2(111)2 ，包含 111 的个数为 333 个，所以 777 是有趣的。但是 9=(1001)29=(1001)_29=(1001)2 包含 222 个 111，所以 999 不是有趣的。
给定正整数 l,rl,rl,r，请你统计满足 l≤n≤rl\le n\le rl≤n≤r 的有趣的整数 nnn 之和。
输入格式
一行，两个正整数 l,rl,rl,r，表示给定的正整数。
输出格式
一行，一个正整数，表示 l,rl,rl,r 之间有趣的整数之和。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
【数据范围】
对于 40%40\%40% 的测试点，保证 1≤l≤r≤1041\le l\le r\le 10^41≤l≤r≤104。
对于另外 30%30\%30% 的测试点，保证 l=1l=1l=1 并且 r=2k−1r=2^k-1r=2k−1，其中 kkk 是大于 111 的正整数。
对于所有测试点，保证 1≤l≤r≤1091 \le l\le r\le 10^91≤l≤r≤109。
【提示】
由于本题的数据范围较大，整数类型请使用 long long。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
[GESP202509 五级] 数字选取
题目描述
给定正整数 nnn，现在有 1,2,…,n1,2,\ldots,n1,2,…,n 共计 nnn 个整数。你需要从这 nnn 个整数中选取一些整数，使得所选取的整数中任意两个不同的整数均互质（也就是说，这两个整数的最大公因数为 111）。请你最大化所选取整数的数量。
例如，当 n=9n=9n=9 时，可以选择 1,5,7,8,91,5,7,8,91,5,7,8,9 共计 555 个整数。可以验证不存在数量更多的选取整数的方案。
输入格式
一行，一个正整数 nnn，表示给定的正整数。
输出格式
一行，一个正整数，表示所选取整数的最大数量。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
对于 40%40\%40% 的测试点，保证 1≤n≤10001\le n\le 10001≤n≤1000。
对于所有测试点，保证 1≤n≤1051\le n\le 10^51≤n≤105。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六级：
[GESP202509 六级] 货物运输
题目描述
A 国有 nnn 座城市，依次以 1,2,…,n1,2,\ldots,n1,2,…,n 编号，其中 111 号城市为首都。这 nnn 座城市由 n−1n-1n−1 条双向道路连接，第 iii 条道路（1≤i<n1 \le i < n1≤i<n）连接编号为 ui,viu_i,v_iui ,vi 的两座城市，道路长度为 lil_ili 。任意两座城市间均可通过双向道路到达。
现在 A 国需要从首都向各个城市运送货物。具体来说，满载货物的车队会从首都开出，经过一座城市时将对应的货物送出，因此车队需要经过所有城市。A 国希望你设计一条路线，在从首都出发经过所有城市的前提下，最小化经过的道路长度总和。注意一座城市可以经过多次，车队最后可以不返回首都。
输入格式
第一行，一个正整数 nnn，表示 A 国的城市数量。
接下来 n−1n-1n−1 行，每行三个正整数 ui,vi,liu_i,v_i,l_iui ,vi ,li ，表示一条双向道路连接编号为 ui,viu_i,v_iui ,vi 的两座城市，道路长度为 lil_ili 。
输出格式
一行，一个整数，表示你设计的路线所经过的道路长度总和。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
对于 30%30\%30% 的测试点，保证 1≤n≤81 \le n \le 81≤n≤8。
对于另外 30%30\%30% 的测试点，保证仅与一条双向道路连接的城市恰有两座。
对于所有测试点，保证 1≤n≤1051 \le n \le 10^51≤n≤105，1≤ui,vi≤n1 \le u_i,v_i \le n1≤ui ,vi ≤n，1≤li≤1091 \le l_i \le 10^91≤li ≤109。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
[GESP202509 六级] 划分字符串
题目描述
小 A 有一个由 nnn 个小写字母组成的字符串 sss。他希望将 sss 划分为若干个子串，使得子串中每个字母至多出现一次。例如，对于字符串 street 来说，str + e + e + t 是满足条件的划分；而 s + tree + t 不是，因为子串 tree 中 e 出现了两次。
额外地，小 A 还给出了价值 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an ，表示划分后长度为 iii 的子串价值为 aia_iai 。小 A 希望最大化划分后得到的子串价值之和。你能帮他求出划分后子串价值之和的最大值吗？
输入格式
第一行，一个正整数 nnn，表示字符串的长度。
第二行，一个包含 nnn 个小写字母的字符串 sss。
第三行，nnn 个正整数 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an ，表示不同长度的子串价值。
输出格式
一行，一个整数，表示划分后子串价值之和的最大值。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
对于 40%40\%40% 的测试点，保证 1≤n≤1031\le n\le 10^31≤n≤103。
对于所有测试点，保证 1≤n≤1051\le n\le 10^51≤n≤105，1≤ai≤1091\le a_i\le 10^91≤ai ≤109。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七级：
[GESP202509 七级] 连通图
题目描述
给定一张包含 nnn 个结点与 mmm 条边的无向图，结点依次以 1,2,…,n1,2,\ldots,n1,2,…,n 编号，第 iii 条边（1≤i≤m1\le i\le m1≤i≤m）连接结点 uiu_iui 与结点 viv_ivi 。如果从一个结点经过若干条边可以到达另一个结点，则称这两个结点是连通的。
你需要向图中加入若干条边，使得图中任意两个结点都是连通的。请你求出最少需要加入的边的条数。
注意给出的图中可能包含重边与自环。
输入格式
第一行，两个正整数 n,mn,mn,m，表示图的点数与边数。
接下来 mmm 行，每行两个正整数 ui,viu_i,v_iui ,vi ，表示图中一条连接结点 uiu_iui 与结点 viv_ivi 的边。
输出格式
输出一行，一个整数，表示使得图中任意两个结点连通所需加入的边的最少数量。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
对于 40%40\%40% 的测试点，保证 1≤n≤1001\le n\le 1001≤n≤100，1≤m≤1001\le m\le 1001≤m≤100。
对于所有测试点，保证 1≤n≤1051\le n\le 10^51≤n≤105，1≤m≤1051\le m\le 10^51≤m≤105。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
[GESP202509 七级] 金币收集
题目描述
小 A 正在游玩收集金币的游戏。具体来说，在数轴上将会出现 nnn 枚金币，其中第 iii 枚（1≤i≤n1\le i\le n1≤i≤n）金币将会在时刻 tit_iti 出现在数轴上坐标为 xix_ixi 的位置。小 A 必须在时刻 tit_iti 恰好位于坐标 xix_ixi ，才可以获得第 iii 枚金币。
游戏开始时为时刻 000，此时小 A 的坐标为 000。正常来说，小 A 可以按游戏机的按键在数轴上左右移动，但不幸的是游戏机的左方向键失灵了。小 A 每个时刻只能选择保持不动，或是向右移动一个单位。换言之，如果小 A 在时刻 ttt 的坐标为 xxx，那么他在时刻 t+1t+1t+1 的坐标只能是 xxx 或是 x+1x+1x+1 二者之一，分别对应保持不动和向右移动。
小 A 想知道他最多能收集多少枚金币。你能帮他收集最多的金币吗？
输入格式
第一行，一个正整数 nnn，表示金币的数量。
接下来 nnn 行，每行两个正整数 xi,tix_i,t_ixi ,ti ，分别表示金币出现的坐标与时刻。
输出格式
输出一行，一个整数，表示小 A 最多能收集的金币数量。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
对于 40%40\%40% 的测试点，保证 1≤n≤81\le n\le 81≤n≤8。
对于另外 30%30\%30% 的测试点，保证 1≤n≤1001\le n\le 1001≤n≤100，1≤xi≤1001\le x_i\le 1001≤xi ≤100，1≤ti≤1001\le t_i\le 1001≤ti ≤100。
对于所有测试点，保证 1≤n≤1051\le n\le 10^51≤n≤105，1≤xi≤1091\le x_i\le 10^91≤xi ≤109，1≤ti≤1091\le t_i\le 10^91≤ti ≤109。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八级：
[GESP202509 八级] 最短距离
题目描述
给定正整数 p,qp,qp,q 以及常数 N=1018N=10^{18}N=1018。现在构建一张包含 NNN 个结点的带权无向图，结点依次以 1,2,…,N1,2,\ldots,N1,2,…,N 编号。对于任意满足 1≤u<v≤N1\le u<v\le N1≤u<v≤N 的 u,vu,vu,v，向图中加入一条连接结点 uuu 与结点 vvv 的无向边，边权取决于 u,vu,vu,v 是否互质：
* 若 u,vu,vu,v 互质（即 u,vu,vu,v 的最大公因数为 111），则连接结点 uuu 与结点 vvv 的无向边长度为 ppp；
* 否则连接结点 uuu 与结点 vvv 的无向边长度为 qqq。
现在给定 nnn 组询问，第 iii（1≤i≤n1\le i\le n1≤i≤n）组询问给定两个正整数 ai,bia_i,b_iai ,bi ，你需要回答结点 aia_iai 与结点 bib_ibi 之间的最短距离。
输入格式
第一行，三个正整数 n,p,qn,p,qn,p,q，分别表示询问数量，结点编号互质时的边权，以及结点编号不互质时的边权。
接下来 nnn 行，每行两个正整数 ai,bia_i,b_iai ,bi ，表示一组询问。
输出格式
输出共 nnn 行，每行一个整数，表示结点 aia_iai 与结点 bib_ibi 之间的最短距离。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
对于 30%30\%30% 的测试点，保证 1≤n≤101\le n\le 101≤n≤10，1≤ai,bi≤501\le a_i,b_i\le 501≤ai ,bi ≤50。
对于另外 30%30\%30% 的测试点，保证 1≤ai,bi≤2501\le a_i,b_i\le 2501≤ai ,bi ≤250。
对于所有测试点，保证 1≤n≤1041\le n\le 10^41≤n≤104，1≤ai,bi≤1091\le a_i,b_i\le 10^91≤ai ,bi ≤109，1≤p,q≤1091\le p,q\le 10^91≤p,q≤109。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
[GESP202509 八级] 最短距离
题目描述
给定正整数 p,qp,qp,q 以及常数 N=1018N=10^{18}N=1018。现在构建一张包含 NNN 个结点的带权无向图，结点依次以 1,2,…,N1,2,\ldots,N1,2,…,N 编号。对于任意满足 1≤u<v≤N1\le u<v\le N1≤u<v≤N 的 u,vu,vu,v，向图中加入一条连接结点 uuu 与结点 vvv 的无向边，边权取决于 u,vu,vu,v 是否互质：
* 若 u,vu,vu,v 互质（即 u,vu,vu,v 的最大公因数为 111），则连接结点 uuu 与结点 vvv 的无向边长度为 ppp；
* 否则连接结点 uuu 与结点 vvv 的无向边长度为 qqq。
现在给定 nnn 组询问，第 iii（1≤i≤n1\le i\le n1≤i≤n）组询问给定两个正整数 ai,bia_i,b_iai ,bi ，你需要回答结点 aia_iai 与结点 bib_ibi 之间的最短距离。
输入格式
第一行，三个正整数 n,p,qn,p,qn,p,q，分别表示询问数量，结点编号互质时的边权，以及结点编号不互质时的边权。
接下来 nnn 行，每行两个正整数 ai,bia_i,b_iai ,bi ，表示一组询问。
输出格式
输出共 nnn 行，每行一个整数，表示结点 aia_iai 与结点 bib_ibi 之间的最短距离。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
对于 30%30\%30% 的测试点，保证 1≤n≤101\le n\le 101≤n≤10，1≤ai,bi≤501\le a_i,b_i\le 501≤ai ,bi ≤50。
对于另外 30%30\%30% 的测试点，保证 1≤ai,bi≤2501\le a_i,b_i\le 2501≤ai ,bi ≤250。
对于所有测试点，保证 1≤n≤1041\le n\le 10^41≤n≤104，1≤ai,bi≤1091\le a_i,b_i\le 10^91≤ai ,bi ≤109，1≤p,q≤1091\le p,q\le 10^91≤p,q≤109。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
[GESP202509 八级] 最小生成树
题目描述
给定一张包含 nnn 个结点 mmm 条边的带权连通无向图，结点依次以 1,2,…,n1,2,\ldots,n1,2,…,n 编号，第 iii 条边（1≤i≤m1\le i\le m1≤i≤m）连接结点 uiu_iui 与结点 viv_ivi ，边权为 wiw_iwi 。
对于每条边，请你求出从图中移除该条边后，图的最小生成树中所有边的边权和。特别地，若移除某条边后图的最小生成树不存在，则输出 −1-1−1。
输入格式
第一行，两个正整数 n,mn,mn,m，分别表示图的结点数与边数。
接下来 mmm 行中的第 iii 行（1≤i≤m1\le i\le m1≤i≤m）包含三个正整数 ui,vi,wiu_i,v_i,w_iui ,vi ,wi ，表示图中连接结点 uiu_iui 与结点 viv_ivi 的边，边权为 wiw_iwi 。
输出格式
输出共 mmm 行，第 iii 行（1≤i≤m1\le i\le m1≤i≤m）包含一个整数，表示移除第 iii 条边后，图的最小生成树中所有边的边权和。若移除第 iii 条边后图的最小生成树不存在，则输出 −1−1−1。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
子任务编号 测试点占比 nnn mmm 特殊性质 1 20%20\%20% ≤50\le 50≤50 ≤100\le 100≤100 - 2 30%30\%30% ≤105\le 10^5≤105 ≤105\le 10^5≤105 n=mn=mn=m 3 30%30\%30% ≤500\le 500≤500 ≤2×104\le 2\times 10^4≤2×104 - 4 20%20\%20% ≤105\le 10^5≤105 ≤105\le 10^5≤105 -
对于所有测试点，保证 1≤n≤1051\le n\le 10^51≤n≤105，1≤m≤1051\le m\le 10^51≤m≤105，1≤ui,vi≤n1\le u_i,v_i\le n1≤ui ,vi ≤n，1≤wi≤1091\le w_i\le 10^91≤wi ≤109。
我也有底线 ^_^，至于 Markdown 吗，有空我发出来。。。
