这是一道模板题
首先，对任意时刻，\(u\)->\(v\)这条路径上的点都是不会变动的（就是说，比如，如果某时刻从\(1\)到\(4\)的路径为\(1\)->\(3\)->\(4\)，那么对之后的任意时刻，这条路径都是这个，既不会改变顺序，也不会新增节点，更不会删除已有节点），所以我们可以把所有有效的操作一存起来最后再建边
那么这里利用倍增优化建边
倍增的分治结构是什么？
这个分治的状态是不是就出来了？注意绿边的边权为0
比如说我现在有一个传送门，是从\(x_0\)->\(x_1\)这条链到\(x_2\)->\(x_4\)这条链，那么我就会从\(f[x_0][0]\)的out点连一条边权为\(w\)的出边到虚拟节点\(T\)，再从\(T\)连一条边权为0的入边到\(f[x_2][1]\)的in点，由于绿边的边权为0，显然就等价于从\(x_0\)->\(x_1\)这条链上的每一个点都连了一条边权为\(w\)的出边到\(x_2\)->\(x_4\)这条链上的每一个点
那么这个的复杂度是多少？首先考虑树上的边，总共是\(o(m)\)条，然后考虑绿边，因为每个树上的点顶多向上跳\(logn\)次，所以in点和out点的个数就是\(O(nlogn)\)，由前文描述可得每个in点和out点至多会连三条有向边，所以绿边的个数就是\(O(nlogn)\)，然后在考虑虚拟节点的边，对每一次操作，我们最多跳\(logn\)步，每跳一步就会连边，所以一共是\(O(mlogn)\)的条边，最后跑dij，总共的时间复杂度为\(O((nlogn+mlogn)logn)\)
考虑优化，利用st表的思想，对一条长度为\(2^k+p\)的链，我们将其分成两步，前\(2^k\)和后\(2^k\)个节点的in点和out点分别按照上述方法连边，尽管有重复连边，但是不影响答案，时间复杂度被优化到了\(O((nlogn+m)logn)\)
什么时候空了写一下代码，把注意的事项都标注上去
其他的优化建边
标签：绿边,边权,logn,nlogn,节点,森林,out From： https://www.cnblogs.com/dingxingdi/p/17901344.html