https://codeforces.com/problemset/problem/487/E

?

題意：

已知一張n個點m條邊的圖，每個點有點權，我們有q次操作，有兩種操作，

第一種是改變一個點的點權；第二種是詢問兩點之間可能走過的簡單路徑中的所有點的最小點權。

n,m,q都是1e5量級。

題解：

遇到這種圖上簡單路徑問題應該考慮建出圓方樹，使用Tarjan算法。

每個方點用一個multiset維護權重。

對于每個方點，只維護方點兒子的最小值，不維護方點父親的值。

對于所有方點，不去維護它在圓方樹上的父親，那么對于每一次修改，只會波及它在圓方樹上的方點父親。

在圓方樹上，兩圓點之間的唯一路徑一定經(jīng)過最近公共祖先。

而如果在某一次詢問中兩點之間的最近公共祖先(LCA)為方點，

還需要額外考慮這個點的父親的權值。

最后樹鏈剖分加線段樹維護最小值。