【OI日记】CF838B 题解
题目链接（洛谷）：https://www.luogu.com.cn/problem/CF838B
题目链接（CF）：http://codeforces.com/contest/838/problem/B
我们将图中的有向边分为如下两种：
树边：(u, v) 一定在 u 的子树内。这些边的编号为 1 至 n-1
图边：形如 (u,1) 的边。编号为 n 至 2n-2
处理询问时，我们应该回答从 u 到 v 的最短距离，由于图中的是有向边，所以这个距离并不与 v 到 u 的距离相同。
对于任意一点 x，我们设 dtree[x] 为走树边从 x 到 1 的唯一距离；设 dgrapg[x] 为走图边从 x 到 1 的唯一距离。
现在我们分别考虑以下几种情况：
若 u = v：
最短距离显然为 0。
若 v 在 u 的子树内：
显然，这个最短距离是树边上 u 走到 v 的距离。
若 v 不在 u 的子树内：
我们应该明白，由于图中的边是有向边，因此从 u 走到 v 是一定要先从 u 走回到 1，再从 1 走树边到达 v。
首先我们能很容易地得出，通过图边 (u,1) 走到 1，再从 1 走树边到达 v 是一条合法路径。
那么它是不是最短路径呢？其实不一定。
对于以 u 为根的字数内的每一个节点 k，存在这样的路径：先走树边从 u 到达 k，再从 k 走图边到达 1。这个距离可能是比我们上面讨论的距离短的。题目中保证了每一个节点都有一条图边，因此可以保证这种路径一定合法。
接下来我们考虑如何求得最短路径。
第 1 种情况，显然。
第 2 种情况，我们可以在读完前 n-1 条边后马上对这棵树进行 dfs，计算出每一的节点相对于根节点 1 的深度、距离、从属关系等信息。我们可以使用 LCA(u, v) = u 来判断 v 是否在 u 的子树中。最短路径 dmin=dtree[v] - dtree[u]。
第 3 种情况，对于以 u 为根的子树，我们考虑维护一个最小值，为 min(dtree[x] + dgraph[x]), x∈subtree[u]。这个最小值减去 dtree[u] 再加上 dgraph[v] 即为所求的最短路径。
接下来我们考虑如何对边进行修改。
当一条边 (u,v) 的权值被修改时，若 v ≠ 1，则 v 及 v 的子树内的节点走树边到达 1 的距离都要改变；若 v = 1，则只有节点 u 走图边到达 1 的距离会发生改变。但是，对数据结构引入 ”子树修改“ 较为麻烦。
我们注意到一种性质：在一棵树的任意一棵子树中，子树内节点的 dfs 序是连续的。因此，我们便将 “子树修改” 转化为了 “区间修改”。我们可以考虑使用线段树维护。
我们设 dfn[x] 为节点 x 的 dfs 序；mx[x] 为节点 x 的子树的最大 dfs 序。可以考虑一个简单的树形DP，当然也可以在回溯时记录当前的 idx_dfn。设第 i 条边起点为 a[i]，终点为 b[i]，边权为 c[i]。
依然分两种情况讨论：
若被修改的是图边，只需要对节点 x，即区间 [dfn[x], dfn[x]] 进行修改。
若被修改的是树边，则需要对区间 [dfn[x], mx[x]] 进行修改。
我们将修改边权的问题转化为区间加，则每次增加的值为修改后的边权 w‘ 减去该边的原边权 w，即 w' - w。在修改那条边过后，我们更新这条边的权值，方便下一次的更新操作。
当然，有了 dfs 序，就没必要用 LCA 判断 v 是否在 u 的子树中了。只需要判断 dfn[v]∈[dfn[u], mx[u]] 即可。
完整代码：
