CCF GESP 2026年3月认证 C++ 8级
题目描述
小 A 的消息记录中有 $n$ 条消息，依次以 $1,2,…,n$ 编号。编号小的消息发送时间早于编号大的消息。
一条消息可以引用一条编号小于它的消息，也可以不引用消息。小 A 注意到消息记录里有引用的消息数量不会非常多。消息记录的一个例子是：
- 【消息 1】小 A：有人做了今天的第一题吗？
- 【消息 2】小 A：我第一题 WA 了，可能是什么原因？
- 【消息 3：引用消息 1】小 B：我我我
- 【消息 4：引用消息 2】小 C：我也 WA 了
- 【消息 5：引用消息 2】小 B：是不是没开
long long？ - 【消息 6：引用消息 5】小 A：改了就 AC 了，太厉害了！
对于消息 $i (1≤i≤n)$，小 A 以 $r_i$ 标记消息 i 是否有引用，以及所引用的消息编号。如果 $r_i$>0，则消息 $i$ 为引用了消息 $r_i$；如果 $r_i$=0，则消息 $i$ 没有引用消息。
消息记录里有非常多条消息。为了快速查找所需要的消息，小 A 准备实现一个简单的消息查找工具。消息查找工具任意时刻只能定位恰好一条消息，如果当前位于消息 $i (1≤i≤n)$，那么接下来可以选择以下两种操作之一：
- 定位到消息 $i-1$；
- 如果消息 $i$ 引用了消息 $r_i$，定位到消息 $r_i$。
以上操作可以执行任意次（包括零次）。
小 A 有 $q$ 次询问。在第 $k (1≤k≤q)$ 次询问中，小 A 给出消息编号 $x_k,y_k (y_k<x_k)$。小 A 想知道，如果当前消息查找工具位于 $x_k$，至少需要多少次操作才能定位到消息 $y_k$。
输入格式
第一行，两个正整数 $n,q$，分别表示消息条数与询问次数。
第二行，$n$ 个非负整数 $r_1,r_2,…,r_n$，表示消息的引用关系，具体含义见题目描述。
接下来 $q$ 行中的第 $k$ 行 $(1≤k≤q)$ 包含两个正整数 $x_k,y_k$，表示一次询问。
保证至多只有 1000 条引用消息。
输出格式
输出 $q$ 行，每行一个整数，表示将界面从消息 $x_k$ 切换到消息 $y_k$ 所需的最少操作次数。
样例说明
样例 1
6 3
0 0 1 2 2 5
4 1
6 2
6 32
2
3样例 2
5 5
0 0 0 1 3
4 1
4 2
5 1
5 2
5 31
2
2
2
1数据范围
对于 40% 的测试点，保证 $1≤n≤2000，1≤q≤2000$。
对于所有测试点，保证 $1≤n≤10^5，1≤q≤10^5，0≤r_i<i，1≤y_k<x_k≤n$，保证至多有 1000 条引用消息。
题目描述
给定包含 $n$ 个结点 $m$ 条边的带权无向图 $G$，结点依次以 $1,2,…,n$ 编号。第 $i (1≤i≤m)$ 条边连接编号为 $u_i$ 与 $v_i$ 的两个结点，权值为 $w_i$。
对于指定的 $1≤l≤r≤n$，按以下方式构造图 G 的子图 $G(l,r)$：
- 保留 $G$ 中编号在区间 $[l,r]$ 中的结点。删去其它编号不在 $[l,r]$ 中的结点以及与之相连的边。剩余的结点和边构成子图 $G(l,r)$。
对于 $G(l,r)$ 中的任意结点 $u,v$ 应有 $l≤u,v≤r$。记 u,v 在子图 $G(l,r)$ 上的最短距离为 $d(l,r,u,v)$。特殊地，若 $u,v$ 在子图 $G(l,r)$ 上不连通，则认为 $d(l,r,u,v)=0$。
你需要求出 $\sum_{l=1}^n \sum_{r=l}^n \sum_{u=l}^r \sum_{v=u}^r\,d(l,r,u,v)$ 对 $10^9$ 取模的结果。
- 题目中的英文字母 l 使用了特殊写法 $l$，以避免英文字母 l 与数字 1 混淆。
输入格式
第一行，两个正整数 $n,m$，表示结点数与边数。
接下来 $m$ 行，第 $i (1≤i≤m)$ 行包含三个正整数 $u_i,v_i,w_i$，表示一条连接结点 $u_i,v_i$ 的权值为 $w_i$ 的边。
输出格式
输出一行，一个整数，表示 $\sum_{l=1}^n \sum_{r=l}^n \sum_{u=l}^r \sum_{v=u}^r\,d(l,r,u,v)$ 对 $10^9$ 取模的结果。
样例说明
样例 1
3 2
1 2 1
2 3 29样例 2
4 6
1 2 100
2 3 100
3 4 100
1 3 10
2 4 10
1 4 1784数据范围
对于 40% 的测试点，保证 $2≤n≤20$。
对于所有测试点，保证 $2≤n≤100，2≤m≤\frac{n(n-1)}{2}，1≤u_i,v_i≤n，1≤w_i≤10^6$。图中可能存在重边。