题目简述：给定一棵$N leq 10^5$个节点的树，边上带权，维护以下两个操作：
1. 修改一条边的边权；
2. 询问当前树的直径长度。
解1：code
注意到树的直径有以下性质：
定理：令$ ext{farthest}(x)$表示与节点$x$距离最远的节点的集合。则对任意节点$x$，都有任意$a in ext{farthest}(x)$与$b in ext{farthest}(a)$，$a$与$b$的距离即为直径。
我们任选一个节点$r$作为树的根，任意边$(x, y)$，若$x$为$y$的父节点，则把边权置于节点$y$上，视作点权，记作$w[y]$，则修改边权都可以视作修改点权。
我们考虑询问树的直径，可以分成两个步骤：1. 找到离$r$距离最远的叶子节点$x$。2. 找到离$x$距离最远的节点$y$。
1. 找到离$r$距离最远的叶子节点$x$。我们在树的DFS序$p_1, p_2, dots, p_n$上查找$ ext{dis}(r, p_i)$的最大值及其下标$i$，则$x = p_i$。可在$O(log n)$时间复杂度内解决。
2. 找到离$x$距离最远的节点$y$。设$ ext{LCA}(x, y) = u$，则$ ext{dis}(x, y) = ext{dis}(r, x)+ ext{dis}(r, y)-2 ext{dis}(r, u)$。考虑树链剖分，在$x$到$r$的路径中的所有重链中，找到最大的节点$u$，使得$ ext{dis}(r, ext{light}(u))-2 ext{dis}(r, u)$最大，其中$ ext{light}(u)$表示节点$u$的轻链连接出去的后代节点集合（包括$u$本身）。可在$O(log^2 n)$时间复杂度内解决。
接下来考虑修改操作，我们只需要维护
1. 步骤1 的 $ ext{dis}(r, p_i)$。只需要用线段树维护区间整体加减，以及区间最值即可。时间复杂度$O(log n)$。
2. 步骤2 的 $ ext{dis}(r, ext{light}(u))-2 ext{dis}(r, u)$。同样需要用线段树维护区间整体加减，以及区间最值。此外，对于每一个节点$x$，我们都需要一个multiset来维护$ ext{light}(x)$中节点$y$的最大值$ ext{dis}(r, y)$。时间复杂度为$O(log^2 n)$。
于是，我们可以在时间复杂度$O(n + q log^2 n)$内解决。
注：同样做法，Link-Cut Tree可以在$O(n + qlog n)$的时间内解决。
解2：code
如果没有修改操作，这题可以用动态规划来求解。为方便，与解1一样，我们以同样的方式把边权都放在点上。特别地，$w[r] = 0$。设$f[x][0]$表示以$x$为根的子树中的直径长度，$f[x][1]$表示$x$为根的子树中与节点$x$距离最远的节点与$x$的距离 加上 节点$x$的权值$w[x]$。于是，我们有
$$ f[x][0] = max{ max_{y in ext{son}(x)}{f[y][0]}, max_{y_1, y_2 in ext{son}(x), y_1 eq y_2}{f[y_1][1]+f[y_2][1]} }, $$
$$ f[x][1] = max_{y in ext{son}(x)}{ f[y][1] } + w[x]. $$
特别地，若$ ext{son}(x) = emptyset$，则$f[x][0] = 0, f[x][1] = w[x]$；若$ ext{son}(x) = { y }$，则$f[x][0] = max{f[y][0], f[y][1]}, f[x][1] = f[y][1]+w[x]$。
现在，我们考虑动态DP。将整棵树树链剖分之后，令
$$ g[x][0] = maxleft{ max_{y in ext{lightson}(x)}{ f[y][0] }, max_{y_1, y_2 in ext{lightson}(x), y_1 eq y_2} { f[y_1][1]+f[y_2][1] } ight}, $$
$$ g[x][1] = max_{y in ext{lightson}(x)}{f[y][1]}, $$
其中，$ ext{lightson}(x) = ext{son}(x) setminus { ext{heavy}(x) }$，$ ext{heavy}(x)$为节点$x$的重儿子。
简记$y = ext{heavy}(x)$，我们可以得到动态规划方程：
$$ f[x][0] = max{ f[y][0], g[x][0], f[y][1]+g[x][1] }, $$
$$ f[x][1] = max{ f[y][1], g[x][1] } + w[x]. $$
即
$$ egin{bmatrix} 0 & g[x][1] & g[x][0] \ -infty & w[x] & g[x][1]+w[x] \ -infty & -infty & 0 end{bmatrix} * egin{bmatrix} f[y][0] \ f[y][1] \ 0 end{bmatrix} = egin{bmatrix} f[x][0] \ f[x][1] \ 0 end{bmatrix}, $$
其中$C = A*B$定义为$C_{ij} = max_k { A_{ik}+B_{kj} }$。
于是，我们可用树链剖分在$O(n + q log^2 n)$的时间复杂度内解决。
注：同样做法，Link-Cut Tree可以在$O(n + qlog n)$的时间内解决。
再注：事实上矩阵的第一列和最后一行在进行广义乘法时是不变的，即结果矩阵永远形如
$$ egin{bmatrix} 0 & * & * \ -infty & * & * \ -infty & -infty & 0 end{bmatrix}. $$
于是，我们只需要计算上述矩阵中打$*$的部分，见code。
解3：code
有一个非常巧妙的做法，考虑树的全DFS序（长度为$2n-1$的DFS序，允许一个节点在这个DFS序中出现多次）$p_1, p_2, p_3, dots, p_{2n-1}$。
令$ ext{index}(x)$表示在全DFS序上节点$x$第一次出现的下标，即$p_{ ext{index}(x)} = x$。
考虑两个节点$x$和$y$，其下标$a = ext{index}(x), b = ext{index}(y)$，不妨设$a leq b$。这两个节点之间的距离
$$egin{aligned} ext{dis}(x, y) & = ext{dis}(r, x)+ ext{dis}(r, y)-2 ext{dis}(r, ext{LCA}(x, y)) \ & = ext{dis}(r,x)+ ext{dis}(r,y)-2min_{a leq c leq b}{ ext{dis}(r, p_c) }. end{aligned}$$
于是，树的直径则为
$$ max_{x, y}{ ext{dis}(x,y)} = max_{1 leq a leq c leq b leq 2n-1 } { ext{dis}(r, p_a)+ ext{dis}(r, p_b)-2 ext{dis}(r, p_c) }. $$
我们可以用线段树维护全DFS序在区间上的信息来解决此题，时间复杂度$O(n+q log n)$。