概要
別解法っぽい？（公式解説が読解できていない）
解法
重心分解により解くことができます。
$N$ 頂点の木 $G$ において重心を $c_G$ とします。
- $e\in G$ に含まれる辺の長さの変更
- $v\in G$ に対して、$v$ を始点とする $G$ 内のパスであって $c_G$ を通るものの最大長を答える
という $Q$ 件を、合計 $Q\log N$ 時間で行うことができます。これによって、元の問題は $O(Q\log^2Q)$ 時間で解くことができます。重心分解で再帰的に問題を解くとき、同じクエリは $O(\log Q)$ 回しか呼ばれないからです。
重心を根として根付き木と見なします。根から各頂点までの距離を $A[v]$ とすると、根を通るパスの端点 $v, w$ に対して、$v, w$ の距離は $A[v] + A[w]$ で表せます。したがって、各クエリの要請は以下の通りです。
- （変更クエリ）$v$ を根とする部分根付き木の頂点 $w$ に対する $A[w]$ に、一斉に定数を加算する
- （計算クエリ）
- $v$ が根のとき、$A$ の最大値を答える
- $v$ が根でないとき、根に関して $v$ と異なる部分木内の頂点に対する $A$ の最大値を計算し、その値と $A[v]$ の和を答える
Euler Tour（参考：Euler Tour のお勉強）をとれば、おおよそ次の処理ができればよいことが分かります。
- （変更クエリ）$l\leq i < r$ に対して、$A[i]$ に定数を加算する
- （計算クエリ）$i\neq [l,r)$ に対する $A_i$ の最大値を計算する
「$i\neq [l,r)$」 という条件は、「$i\in [0,l)$ または $i \in [r,N)$」と言い換えられるので、これらの処理は、区間加算と区間 $\max$ 取得の行えるセグメント木によって行うことができます。
