发现难点在于维护 \(dis_u\)（起点 \(s\) 到 \(u\) 的最短路）。如果使用暴力高精度，复杂度会乘上一个 \(len\)。考虑边权 \(2^w\) 的特殊性质，如果使用一个二进制串来维护 \(dis\)，那么加上边权 \(2^w\) 相当于将二进制下某一段 \(1\) 置为 \(0\)，然后再将一个 \(0\) 置为 \(1\)。说白了就是区间赋 \(0\)（覆盖） + 单点加，不难想到用线段树维护。Dijkstra 的过程中涉及到加 \(2^w\) 以及比大小的问题，比大小的话在线段树上维护一个区间 hash 值，然后直接线段树二分求 LCP 即可，找全 \(1\) 段就线段树二分，维护一个区间的 \(1\) 个数。
问题来了，每个点开一个线段树维护 \(dis\) 空间一定寄。发现 \(dis\) 的转移只会修改至多 \(\log n\) 个位置，所以用主席树。区间赋 \(0\) 就直接建一个全是 \(0\) 的辅助树，把要覆盖的区间往辅助树上对应区间连就好了。各类主席树上操作都是 \(\mathcal{O}(\log n)\) 的，套一个 Dijkstra 就是 \(\mathcal{O}(n\log^2 n)\)，其中 \(n,m\) 同阶。需要注意线段树上其实是把二进制数倒过来了，运算的时候先右儿子再左儿子。
标签：log,Classic,线段,维护,区间,Problem,树上,CF464E,dis From： https://www.cnblogs.com/Tsukinaga-Ichiyo/p/18147833