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