hdu 6393Traffic Network in Numazu 基环外向树 LCA 树

题意就是,给你一个基环外向树,然后问任意两点间最短路,有修改边权,nlogn做法。

然后就在环上随便删一个遍,然后我们lca求最短路,再看经过删掉的边的距离,取个min就好了。这题数据很有趣,最后一条边一定在环上,可以少写一个dfs……

然后怎么修改边权,线段树按照dfs序维护一[……]

Read more