2024.8 - Record of Questions and Summary of Methodology
先分享一个歌单：
永无止境的八月！
2024/08/01
先来点重量级的
P4768 [NOI2018] 归程
题面：
[NOI2018] 归程
题目描述
本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。
魔力之都可以抽象成一个 \(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 \mathrm{lastans} - 1) \bmod n + 1\)。
- 这一天的水位线为 \(p = (p_0 + K \times \mathrm{lastans}) \bmod (S + 1)\)。
其中 \(\mathrm{lastans}\) 表示上一天的答案（最小步行总路程）。特别地，我们规定第 \(1\) 天时 \(\mathrm{lastans} = 0\)。
在这里，我们保证 \(1 \leq v_0 \leq n\)，\(0 \leq p_0 \leq S\)。对于输入中的每一行，如果该行包含多个数，则用单个空格将它们隔开。
输出格式
依次输出各组数据的答案。对于每组数据：
- 输出 \(Q\) 行每行一个整数，依次表示每天的最小步行总路程。
样例 #1
样例输入 #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
样例输入 #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提示
更多样例
更多样例请在附加文件中下载。
样例 3
见附加文件中的
return3.in与return3.ans。该样例满足海拔为一种，且不强制在线。
样例 4
见附加文件中的
return4.in与return4.ans。该样例满足图形态为一条链，且强制在线。
样例 5
见附加文件中的
return5.in与return5.ans。该样例满足不强制在线。
样例 1 解释
第一天没有降水，Yazid 可以坐车直接回到家中。
第二天、第三天、第四天的积水情况相同，均为连接 1，2 号节点的边、连接 3，4 号点的边有积水。
对于第二天，Yazid 从 2 号点出发坐车只能去往 3 号节点，对回家没有帮助。因此 Yazid 只能纯靠徒步回家。
对于第三天，从 4 号节点出发的唯一一条边是有积水的，车也就变得无用了。Yazid 只能纯靠徒步回家。
对于第四天，Yazid 可以坐车先到达 2 号节点，再步行回家。
第五天所有的边都积水了，因此 Yazid 只能纯靠徒步回家。
样例 2 解释
本组数据强制在线。
第一天的答案是 \(0\)，因此第二天的 \(v=\left( 5+0-1\right)\bmod 5+1=5\)，\(p=\left(2+0\right)\bmod\left(3+1\right)=2\)。
第二天的答案是 \(2\)，因此第三天的 \(v=\left( 2+2-1\right)\bmod 5+1=4\)，\(p=\left(0+2\right)\bmod\left(3+1\right)=2\)。
第三天的答案是 \(3\)，因此第四天的 \(v=\left( 4+3-1\right)\bmod 5+1=2\)，\(p=\left(0+3\right)\bmod\left(3+1\right)=3\)。
数据范围与约定
所有测试点均保证 \(T\leq 3\)，所有测试点中的所有数据均满足如下限制：
- \(n\leq 2\times 10^5\)，\(m\leq 4\times 10^5\)，\(Q\leq 4\times 10^5\)，\(K\in\left\{0,1\right\}\)，\(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 不保证 不保证 是
kruskal 重构树！
这个东西太 inba 了,在做kruskal的时候建新点，点权为最小/大生成树上的边权
搬自 luogu日报（OI-Wiki）
强大性质：原图中两个点间所有路径上的边最大权值的最小值，最小生成树上两点简单路径的边最大权值 ，Kruskal 重构树上两点 LCA 的点权。