【OI日記】CF838B 題解
題目鏈接（洛谷）：https://www.luogu.com.cn/problem/CF838B
題目鏈接（CF）：http://codeforces.com/contest/838/problem/B
我們將圖中的有向邊分為如下兩種：
樹邊：(u, v) 一定在 u 的子樹內(nèi)。這些邊的編號(hào)為 1 至 n-1
圖邊：形如 (u,1) 的邊。編號(hào)為 n 至 2n-2
處理詢問時(shí)，我們應(yīng)該回答從 u 到 v 的最短距離，由于圖中的是有向邊，所以這個(gè)距離并不與 v 到 u 的距離相同。
對(duì)于任意一點(diǎn) x，我們設(shè) dtree[x] 為走樹邊從 x 到 1 的唯一距離；設(shè) dgrapg[x] 為走圖邊從 x 到 1 的唯一距離。
現(xiàn)在我們分別考慮以下幾種情況：
若 u = v：
最短距離顯然為 0。
若 v 在 u 的子樹內(nèi)：
顯然，這個(gè)最短距離是樹邊上 u 走到 v 的距離。
若 v 不在 u 的子樹內(nèi)：
我們應(yīng)該明白，由于圖中的邊是有向邊，因此從 u 走到 v 是一定要先從 u 走回到 1，再從 1 走樹邊到達(dá) v。
首先我們能很容易地得出，通過圖邊 (u,1) 走到 1，再從 1 走樹邊到達(dá) v 是一條合法路徑。
那么它是不是最短路徑呢？其實(shí)不一定。
對(duì)于以 u 為根的字?jǐn)?shù)內(nèi)的每一個(gè)節(jié)點(diǎn) k，存在這樣的路徑：先走樹邊從 u 到達(dá) k，再從 k 走圖邊到達(dá) 1。這個(gè)距離可能是比我們上面討論的距離短的。題目中保證了每一個(gè)節(jié)點(diǎn)都有一條圖邊，因此可以保證這種路徑一定合法。
接下來我們考慮如何求得最短路徑。
第 1 種情況，顯然。
第 2 種情況，我們可以在讀完前 n-1 條邊后馬上對(duì)這棵樹進(jìn)行 dfs，計(jì)算出每一的節(jié)點(diǎn)相對(duì)于根節(jié)點(diǎn) 1 的深度、距離、從屬關(guān)系等信息。我們可以使用 LCA(u, v) = u 來判斷 v 是否在 u 的子樹中。最短路徑 dmin=dtree[v] - dtree[u]。
第 3 種情況，對(duì)于以 u 為根的子樹，我們考慮維護(hù)一個(gè)最小值，為 min(dtree[x] + dgraph[x]), x∈subtree[u]。這個(gè)最小值減去 dtree[u] 再加上 dgraph[v] 即為所求的最短路徑。
接下來我們考慮如何對(duì)邊進(jìn)行修改。
當(dāng)一條邊 (u,v) 的權(quán)值被修改時(shí)，若 v ≠ 1，則 v 及 v 的子樹內(nèi)的節(jié)點(diǎn)走樹邊到達(dá) 1 的距離都要改變；若 v = 1，則只有節(jié)點(diǎn) u 走圖邊到達(dá) 1 的距離會(huì)發(fā)生改變。但是，對(duì)數(shù)據(jù)結(jié)構(gòu)引入 ”子樹修改“ 較為麻煩。
我們注意到一種性質(zhì)：在一棵樹的任意一棵子樹中，子樹內(nèi)節(jié)點(diǎn)的 dfs 序是連續(xù)的。因此，我們便將 “子樹修改” 轉(zhuǎn)化為了 “區(qū)間修改”。我們可以考慮使用線段樹維護(hù)。
我們設(shè) dfn[x] 為節(jié)點(diǎn) x 的 dfs 序；mx[x] 為節(jié)點(diǎn) x 的子樹的最大 dfs 序?？梢钥紤]一個(gè)簡單的樹形DP，當(dāng)然也可以在回溯時(shí)記錄當(dāng)前的 idx_dfn。設(shè)第 i 條邊起點(diǎn)為 a[i]，終點(diǎn)為 b[i]，邊權(quán)為 c[i]。
依然分兩種情況討論：
若被修改的是圖邊，只需要對(duì)節(jié)點(diǎn) x，即區(qū)間 [dfn[x], dfn[x]] 進(jìn)行修改。
若被修改的是樹邊，則需要對(duì)區(qū)間 [dfn[x], mx[x]] 進(jìn)行修改。
我們將修改邊權(quán)的問題轉(zhuǎn)化為區(qū)間加，則每次增加的值為修改后的邊權(quán) w‘ 減去該邊的原邊權(quán) w，即 w' - w。在修改那條邊過后，我們更新這條邊的權(quán)值，方便下一次的更新操作。
當(dāng)然，有了 dfs 序，就沒必要用 LCA 判斷 v 是否在 u 的子樹中了。只需要判斷 dfn[v]∈[dfn[u], mx[u]] 即可。
完整代碼：
