%%%

先处理完所有删边操作，再逆序处理所有操作（原来的删边处理时改为添边）。
维护一个带权并查集（所谓的权就是会不会走到环路）。
最后一个点用递归find()会爆栈，改迭代find()就可以了。

回复 @liu_runda :
表示一棵线段树三个点之后都超时，怎么优化？

一遍过

注意几个坑点：
1.答案要用long long
2.有重边，以较短的的为准

这个超时……

又是考试原题，卧槽！！！！

[size=32] ^_^ [/size]

回复 @stone :
快使用流加速哼哼哈嘿

写了两棵线段树.......貌似考试时只有我A了？一棵线段树保存不跳过任何检查站时的路径长度，一棵线段树保存某段子赛程中跳过检查站所能缩短的最大距离。不过这算法还是略慢啊。

裸匈牙利水之

文章开头可能有多余空格.....

回复 @叶子の宿敌 :
快速傅里叶变换可以在NlogN时间内执行高精度乘法，另外用牛顿迭代法可以将高精度除法和高精度开方转换为高精度乘法，总时间复杂度N（logN）^2

。。。一道水题。。。我居然~~TM水了三遍才过！！！！！！！！！！！

基本是照课本打的。。。滚动数组要从后向前计算我还没记住.....

[size=32]不要方 结果是long long[/size]