偶然看到了 这道题,求的是边权为 \(n^w\) 次方时树上的第 \(k\) 小路径,觉得这类题目很有意思,就研究了一下。
题意:给一个无向图,每条边的边权是 \(2^{w_i}\),求 \(s\) 到 \(t\) 的最短路。
思路:首先,我们可以把距离看成一个二进制数,那么我们需要能支持快速比较两个二进制数,二进制数在某一位 +1,把一个二进制数赋成另一个二进制数的数据结构。
因为有最后一个操作,好像只有可持久化的数据结构支持这一点,于是考虑用主席树来维护。
对于第一个操作,需要维护每个区间的哈希值,比较时找出两个二进制数的 lcp 就可以比较大小。
对于第二个操作,需要能查一个位置后面第一个是 0 的位置和区间清零,前者可以用主席树上二分,后者可以直接把一个空的主席树复制过来。
接下来的部分就比较简单了。直接用 dijkstra,每个点维护一棵主席树,松弛边 \((u,v,w)\) 的时候就是新建一棵主席树表示 \(dis_u+2^w\),然后判断和 \(dis_v\) 的大小关系即可。
题意:有一棵树,每条边的边权为 \(n^{w_i}\) 次方时树上的第 \(k\) 小路径。
思路:因为边权是 \(n^z\),而一条路径最多只有 \(n-1\) 条边,因此不用考虑进位的问题,只用考虑每个 \(n^i\) 的系数。
首先,肯定要二分答案,但是值域太大不好直接二分,但是一共只有 \(\dfrac{n(n-1)}{2}\) 条路径,可以考虑直接二分路径,同时采用随机二分。
然后就是怎么判断一条路径在路径集合中的排名。
处理树上路径一般采用点/边分治,这道题用边分治更好处理,于是可以先用边分治处理处所有一半的路径,然后排序,二分判段时双指针计算答案即可。
如何维护每条路径的系数和比较大小呢?和上一题一样,可以把边权看成一个 \(n\) 进制数,然后使用主席树。主席树上叶子节点维护 \(n_i\) 的系数,每个节点都维护当前区间表示的数的哈希值,就可以支持维护路径的系数和比较大小了。
其实这类问题思维量算是紫题的水平,但是困难点就在于代码实现,比如第二题代码长度达到了 6.6k。