图论

关于 SPFA: 它死了。

[NOI2019] 弹跳

个点，点有坐标，点 向所有满足 的 连边权为 的边。求 号点到其余各点的最短路。

不会 。洛谷题解里有高妙的 做法。

众所周知，对于一维的情况可以使用线段树优化建图。

那么，对于二维就可以二维线段树优化建图了！（这不废话吗。）

套路地对于每个弹跳装置建一个虚拟节点，对应原图上的起点向其连边权为 的边，出边边权为 。

而二维线段树的实现方式主要有两种：树套树和四分树。

树套树空间双 完美被卡，四分树复杂度又不对。

处理二维情况还有其它办法吗？

发现我们只需要访问矩形内部的点。因此，我们可以考虑在线段树上每个节点维护一个 ，松弛时直接二分出所有 更新。而根据 的性质，无论松弛是否成功，可以直接删去这个点。

考虑证明。

只有虚拟节点需要进行矩形查询，而所有虚拟节点出边边权全部相等，并且 优先选择距离最小的点进行增广，因此只有最先访问到的才有可能成为最短路。

然后就简单了。时间复杂度 ，常数略大。

[NOI2021] 轻重边

题意很清楚。

第一眼看到还以为是 CF1749F 的弱化版，尝试使用类似的方法。然后发现推平操作不支持拆分。寄。

考虑树剖。先把边的询问转化成对点的询问。

我们可以为点赋上点权。对于一条边 ， 是一条重边。

于是修改操作可以直接区间推平。

现在我们需要查询路径上有多少相邻的同色点对。很简单，线段树维护答案和左右端点权值，合并子节点信息的时候判是否加一即可。

[NOI2021] 庆典

有向图上的可达性问题，首先考虑缩点。

注意到特殊性质：

对于三座城市 ，，，若 且 ，那么有 或 。

这说明原图中只有一个入度为 的点。再加上“将边视为无向边后图联通”，缩点完的 应该是一棵外向树。可能有从祖先到儿子的边，但这些边可以忽略，毕竟要经过点数尽可能多。

缩点后拓扑排序，删去某个点最后一条入边的点设为其父亲即可。

那么，对于没有额外边的情况我们就可以很轻松地解决了！只能祖先到孩子，因此判断一下终点是否在起点子树内，做根节点向下总点数的前缀和就好了。

对于额外边，考虑维护从 可以到达的点以及可以到达 的点，两个点集取交即可。

可以树剖维护，查询完直接清空可以避免算重。

CF587D Duff in Mafia

最大边权最小，首先二分答案。

剩下有若干限制，需要判断每条边选还是不选，考虑 。

限制形如：

• 边权 ：不满足的边 。
• 选出一个匹配：对于共用端点的边（假设编号为 ）， 且 ，连边 。
• 剩下同色边构成匹配：与上面类似，边方向反一下即可。

暴力建边边数是 的。

由于是区间建边，直接上前缀和优化建图。就做完了。

CF1083C Max Mex

脑洞题。

注意到 是可以二分的。