A6551. 「NOI2018」归程
编程题
省选/NOI-
知识点
题目描述
> 本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。
>
> 魔力之都可以抽象成一个 $n$ 个节点、$m$ 条边的**无向连通图**（节点的编号从 $1$ 至 $n$）。我们依次用 $l, a$ 描述一条边的**长度**、**海拔**。
>
> 作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此**有积水的边一定是海拔相对最低的一些边**。
>
> 我们用**水位线**来描述降雨的程度，它的意义是：所有海拔**不超过**水位线的边都是**有积水**的。
Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。
Yazid 的家恰好在魔力之都的 $1$ 号节点。对于接下来 $Q$ 天，每一天 Yazid 都会告诉你他的出发点 $v$，以及当天的水位线 $p$。
每一天，Yazid 在出发点都拥有一辆**车**。这辆车由于一些故障不能经过有积水的边。
Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。
+ 需要特殊说明的是，第二天车会被重置，这意味着：
+ 车会在新的出发点被准备好。
+ Yazid 不能利用之前在某处停放的车。
Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他**步行经过的**边的总长度。请你帮助 Yazid 进行计算。
**本题的部分测试点将强制在线，具体细节请见「输入格式」和「子任务」。**
>
> 魔力之都可以抽象成一个 $n$ 个节点、$m$ 条边的**无向连通图**（节点的编号从 $1$ 至 $n$）。我们依次用 $l, a$ 描述一条边的**长度**、**海拔**。
>
> 作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此**有积水的边一定是海拔相对最低的一些边**。
>
> 我们用**水位线**来描述降雨的程度，它的意义是：所有海拔**不超过**水位线的边都是**有积水**的。
Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。
Yazid 的家恰好在魔力之都的 $1$ 号节点。对于接下来 $Q$ 天，每一天 Yazid 都会告诉你他的出发点 $v$，以及当天的水位线 $p$。
每一天，Yazid 在出发点都拥有一辆**车**。这辆车由于一些故障不能经过有积水的边。
Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。
+ 需要特殊说明的是，第二天车会被重置，这意味着：
+ 车会在新的出发点被准备好。
+ Yazid 不能利用之前在某处停放的车。
Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他**步行经过的**边的总长度。请你帮助 Yazid 进行计算。
**本题的部分测试点将强制在线，具体细节请见「输入格式」和「子任务」。**
输入格式
从文件
单个测试点中包含多组数据。输入的第一行为一个非负整数 $T$，表示数据的组数。
接下来依次描述每组数据，对于每组数据：
+ 第一行 $2$ 个非负整数 $n, m$，分别表示节点数、边数。
+ 接下来 $m$ 行，每行 $4$ 个正整数 $u, v, l, a$，描述一条连接节点 $u, v$ 的、长度为 $l$、海拔为 $a$ 的边。
+ 在这里，我们保证 $1 \leq u, v \leq n$。
+ 接下来一行 $3$ 个非负数 $Q, K, S$，其中：
+ $Q$ 表示总天数，
+ $K \in \{0, 1\}$ 是一个会在下面被用到的系数，
+ $S$ 表示的是可能的最高水位线。
+ 接下来 $Q$ 行依次描述每天的状况。每行 $2$ 个整数 $v_0 , p_0$ 描述一天：
+ 这一天的出发节点为 $v = (v_0 + K \times \text{lastans} − 1) \bmod n + 1$。
+ 这一天的水位线为 $p = (p_0 + K \times \text{lastans} ) \bmod (S + 1)$。
+ 其中 $\text{lastans}$ 表示上一天的答案（最小步行总路程）。特别地，我们规定第 $1$ 天时 $\text{lastans} = 0$。
+ 在这里，我们保证 $1 \leq v_0 \leq n,0 \leq p_0 \leq S$。
对于输入中的每一行，如果该行包含多个数，则用单个空格将它们隔开。
return.in 读入数据。单个测试点中包含多组数据。输入的第一行为一个非负整数 $T$，表示数据的组数。
接下来依次描述每组数据，对于每组数据：
+ 第一行 $2$ 个非负整数 $n, m$，分别表示节点数、边数。
+ 接下来 $m$ 行，每行 $4$ 个正整数 $u, v, l, a$，描述一条连接节点 $u, v$ 的、长度为 $l$、海拔为 $a$ 的边。
+ 在这里，我们保证 $1 \leq u, v \leq n$。
+ 接下来一行 $3$ 个非负数 $Q, K, S$，其中：
+ $Q$ 表示总天数，
+ $K \in \{0, 1\}$ 是一个会在下面被用到的系数，
+ $S$ 表示的是可能的最高水位线。
+ 接下来 $Q$ 行依次描述每天的状况。每行 $2$ 个整数 $v_0 , p_0$ 描述一天：
+ 这一天的出发节点为 $v = (v_0 + K \times \text{lastans} − 1) \bmod n + 1$。
+ 这一天的水位线为 $p = (p_0 + K \times \text{lastans} ) \bmod (S + 1)$。
+ 其中 $\text{lastans}$ 表示上一天的答案（最小步行总路程）。特别地，我们规定第 $1$ 天时 $\text{lastans} = 0$。
+ 在这里，我们保证 $1 \leq v_0 \leq n,0 \leq p_0 \leq S$。
对于输入中的每一行，如果该行包含多个数，则用单个空格将它们隔开。
输出格式
输出到文件
依次输出各组数据的答案。对于每组数据：
+ 输出 $Q$ 行每行一个整数，依次表示每天的最小步行总路程。
return.out 中。依次输出各组数据的答案。对于每组数据：
+ 输出 $Q$ 行每行一个整数，依次表示每天的最小步行总路程。
输入输出样例
输入 #1
1 4 3 1 2 50 1 2 3 100 2 3 4 50 1 5 0 2 3 0 2 1 4 1 3 1 3 2
输出 #1
0 50 200 50 150
输入 #2
1 5 5 1 2 1 2 2 3 1 2 4 3 1 2 5 3 1 2 1 5 2 1 4 1 3 5 1 5 2 2 0 4 0
输出 #2
0 2 3 1
说明/提示
**所有测试点均保证 $T \leq 3$，所有测试点中的所有数据均满足如下限制：**
+ $n \leq 2 \times 10^5$，$m \leq 4 \times 10^5$，$Q \leq 4 \times 10^5$，$K \in \{0, 1\}$，$1 \leq S \leq 10^9$。
+ 对于所有边：$l \leq 10^4$，$a \leq 10^9$。
+ 任意两点之间都直接或间接通过边相连。
**为了方便你快速理解，我们在表格中使用了一些简单易懂的表述。在此，我们对这些内容作形式化的说明：**
+ 图形态：对于表格中该项为「一棵树」或「一条链」的测试点，保证 $m = n − 1$。除此之外，这两类测试点分别满足如下限制：
+ 一棵树：保证输入的图是一棵树，即保证边不会构成回路。
+ 一条链：保证所有边满足 $u + 1 = v$。
+ 海拔：对于表格中该项为「一种」的测试点，保证对于所有边有 $a = 1$。
+ 强制在线：对于表格中该项为「是」的测试点，保证 $K = 1$；如果该项为「否」，则有 $K = 0$。
+ 对于所有测试点，如果上述对应项为「不保证」，则对该项内容不作任何保证。
<!--|$n$|$m$|$Q=$|测试点|图形态|海拔|强制在线|
|:---:|:----:|:-----:|:-------:|:-------:|:----:|:----------:|
|$\leq 1$|$\leq 0$|$0$|$1$|不保证|一种|否|
|$\leq 6$|$\leq 10$|$10$|$2$|不保证|一种|否|
|$\leq 50$|$\leq 150$|$100$|$3$|不保证|一种|否|
|$\leq 100$|$\leq 300$|$200$|$4$|不保证|一种|否|
|$\leq 1500$|$\leq 4000$|$2000$|$5$|不保证|一种|否|
|$\leq 200000$|$\leq 400000$|$100000$|$6$|不保证|一种|否|
|$\leq 1500$|$=n-1$|$2000$|$7$|一条链|不保证|否|
|$\leq 1500$|$=n-1$|$2000$|$8$|一条链|不保证|否|
|$\leq 1500$|$=n-1$|$2000$|$9$|一条链|不保证|否|
|$\leq 200000$|$=n-1$|$100000$|$10$|一棵树|不保证|否|
|$\leq 200000$|$=n-1$|$100000$|$11$|一棵树|不保证|是|
|$\leq 200000$|$\leq 400000$|$100000$|$12$|不保证|不保证|否|
|$\leq 200000$|$\leq 400000$|$100000$|$13$|不保证|不保证|否|
|$\leq 200000$|$\leq 400000$|$100000$|$14$|不保证|不保证|否|
|$\leq 1500$|$\leq 4000$|$2000$|$15$|不保证|不保证|是|
|$\leq 1500$|$\leq 4000$|$2000$|$16$|不保证|不保证|是|
|$\leq 200000$|$\leq 400000$|$100000$|$17$|不保证|不保证|是|
|$\leq 200000$|$\leq 400000$|$100000$|$18$|不保证|不保证|是|
|$\leq 200000$|$\leq 400000$|$400000$|$19$|不保证|不保证|是|
|$\leq 200000$|$\leq 400000$|$400000$|$20$|不保证|不保证|是|-->
<!-- BEGIN: Migrated markdown table -->
| $n$ | $m$ | $Q =$ | 测试点 | 图形态 | 海拔 | 强制在线 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $\leq 1$ | $\leq 0$ | $0$ | 1 | 不保证 | 一种 | 否 |
| $\leq 6$ | $\leq 10$ | $10$ | 2 | 不保证 | 一种 | 否 |
| $\leq 50$ | $\leq 150$ | $100$ | 3 | 不保证 | 一种 | 否 |
| $\leq 100$ | $\leq 300$ | $200$ | 4 | 不保证 | 一种 | 否 |
| $\leq 1500$ | $\leq 4000$ | $2000$ | 5 | 不保证 | 一种 | 否 |
| $\leq 200000$ | $\leq 400000$ | $100000$ | 6 | 不保证 | 一种 | 否 |
| $\leq 1500$ | $= n - 1$ | $2000$ | 7 | 一条链 | 不保证 | 否 |
| $\leq 1500$ | $= n - 1$ | $2000$ | 8 | 一条链 | 不保证 | 否 |
| $\leq 1500$ | $= n - 1$ | $2000$ | 9 | 一条链 | 不保证 | 否 |
| $\leq 200000$ | $= n - 1$ | $100000$ | 10 | 一棵树 | 不保证 | 否 |
| $\leq 200000$ | $= n - 1$ | $100000$ | 11 | 一棵树 | 不保证 | 是 |
| $\leq 200000$ | $\leq 400000$ | $100000$ | 12 | 不保证 | 不保证 | 否 |
| $\leq 200000$ | $\leq 400000$ | $100000$ | 13 | 不保证 | 不保证 | 否 |
| $\leq 200000$ | $\leq 400000$ | $100000$ | 14 | 不保证 | 不保证 | 否 |
| $\leq 1500$ | $\leq 4000$ | $2000$ | 15 | 不保证 | 不保证 | 是 |
| $\leq 1500$ | $\leq 4000$ | $2000$ | 16 | 不保证 | 不保证 | 是 |
| $\leq 200000$ | $\leq 400000$ | $100000$ | 17 | 不保证 | 不保证 | 是 |
| $\leq 200000$ | $\leq 400000$ | $100000$ | 18 | 不保证 | 不保证 | 是 |
| $\leq 200000$ | $\leq 400000$ | $400000$ | 19 | 不保证 | 不保证 | 是 |
| $\leq 200000$ | $\leq 400000$ | $400000$ | 20 | 不保证 | 不保证 | 是 |
为了优化你的阅读体验，我们在表格中把测试点的编号放在了中间，请注意这一点。
+ $n \leq 2 \times 10^5$，$m \leq 4 \times 10^5$，$Q \leq 4 \times 10^5$，$K \in \{0, 1\}$，$1 \leq S \leq 10^9$。
+ 对于所有边：$l \leq 10^4$，$a \leq 10^9$。
+ 任意两点之间都直接或间接通过边相连。
**为了方便你快速理解，我们在表格中使用了一些简单易懂的表述。在此，我们对这些内容作形式化的说明：**
+ 图形态：对于表格中该项为「一棵树」或「一条链」的测试点，保证 $m = n − 1$。除此之外，这两类测试点分别满足如下限制：
+ 一棵树：保证输入的图是一棵树，即保证边不会构成回路。
+ 一条链：保证所有边满足 $u + 1 = v$。
+ 海拔：对于表格中该项为「一种」的测试点，保证对于所有边有 $a = 1$。
+ 强制在线：对于表格中该项为「是」的测试点，保证 $K = 1$；如果该项为「否」，则有 $K = 0$。
+ 对于所有测试点，如果上述对应项为「不保证」，则对该项内容不作任何保证。
<!--|$n$|$m$|$Q=$|测试点|图形态|海拔|强制在线|
|:---:|:----:|:-----:|:-------:|:-------:|:----:|:----------:|
|$\leq 1$|$\leq 0$|$0$|$1$|不保证|一种|否|
|$\leq 6$|$\leq 10$|$10$|$2$|不保证|一种|否|
|$\leq 50$|$\leq 150$|$100$|$3$|不保证|一种|否|
|$\leq 100$|$\leq 300$|$200$|$4$|不保证|一种|否|
|$\leq 1500$|$\leq 4000$|$2000$|$5$|不保证|一种|否|
|$\leq 200000$|$\leq 400000$|$100000$|$6$|不保证|一种|否|
|$\leq 1500$|$=n-1$|$2000$|$7$|一条链|不保证|否|
|$\leq 1500$|$=n-1$|$2000$|$8$|一条链|不保证|否|
|$\leq 1500$|$=n-1$|$2000$|$9$|一条链|不保证|否|
|$\leq 200000$|$=n-1$|$100000$|$10$|一棵树|不保证|否|
|$\leq 200000$|$=n-1$|$100000$|$11$|一棵树|不保证|是|
|$\leq 200000$|$\leq 400000$|$100000$|$12$|不保证|不保证|否|
|$\leq 200000$|$\leq 400000$|$100000$|$13$|不保证|不保证|否|
|$\leq 200000$|$\leq 400000$|$100000$|$14$|不保证|不保证|否|
|$\leq 1500$|$\leq 4000$|$2000$|$15$|不保证|不保证|是|
|$\leq 1500$|$\leq 4000$|$2000$|$16$|不保证|不保证|是|
|$\leq 200000$|$\leq 400000$|$100000$|$17$|不保证|不保证|是|
|$\leq 200000$|$\leq 400000$|$100000$|$18$|不保证|不保证|是|
|$\leq 200000$|$\leq 400000$|$400000$|$19$|不保证|不保证|是|
|$\leq 200000$|$\leq 400000$|$400000$|$20$|不保证|不保证|是|-->
<!-- BEGIN: Migrated markdown table -->
| $n$ | $m$ | $Q =$ | 测试点 | 图形态 | 海拔 | 强制在线 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $\leq 1$ | $\leq 0$ | $0$ | 1 | 不保证 | 一种 | 否 |
| $\leq 6$ | $\leq 10$ | $10$ | 2 | 不保证 | 一种 | 否 |
| $\leq 50$ | $\leq 150$ | $100$ | 3 | 不保证 | 一种 | 否 |
| $\leq 100$ | $\leq 300$ | $200$ | 4 | 不保证 | 一种 | 否 |
| $\leq 1500$ | $\leq 4000$ | $2000$ | 5 | 不保证 | 一种 | 否 |
| $\leq 200000$ | $\leq 400000$ | $100000$ | 6 | 不保证 | 一种 | 否 |
| $\leq 1500$ | $= n - 1$ | $2000$ | 7 | 一条链 | 不保证 | 否 |
| $\leq 1500$ | $= n - 1$ | $2000$ | 8 | 一条链 | 不保证 | 否 |
| $\leq 1500$ | $= n - 1$ | $2000$ | 9 | 一条链 | 不保证 | 否 |
| $\leq 200000$ | $= n - 1$ | $100000$ | 10 | 一棵树 | 不保证 | 否 |
| $\leq 200000$ | $= n - 1$ | $100000$ | 11 | 一棵树 | 不保证 | 是 |
| $\leq 200000$ | $\leq 400000$ | $100000$ | 12 | 不保证 | 不保证 | 否 |
| $\leq 200000$ | $\leq 400000$ | $100000$ | 13 | 不保证 | 不保证 | 否 |
| $\leq 200000$ | $\leq 400000$ | $100000$ | 14 | 不保证 | 不保证 | 否 |
| $\leq 1500$ | $\leq 4000$ | $2000$ | 15 | 不保证 | 不保证 | 是 |
| $\leq 1500$ | $\leq 4000$ | $2000$ | 16 | 不保证 | 不保证 | 是 |
| $\leq 200000$ | $\leq 400000$ | $100000$ | 17 | 不保证 | 不保证 | 是 |
| $\leq 200000$ | $\leq 400000$ | $100000$ | 18 | 不保证 | 不保证 | 是 |
| $\leq 200000$ | $\leq 400000$ | $400000$ | 19 | 不保证 | 不保证 | 是 |
| $\leq 200000$ | $\leq 400000$ | $400000$ | 20 | 不保证 | 不保证 | 是 |
为了优化你的阅读体验，我们在表格中把测试点的编号放在了中间，请注意这一点。