以上はすべて O(N) で行える。
頂点 v を消すとする。まずこれによって変化する S を更新する方法を考える。
この変化の影響を受けるのは R[v] と v を結ぶ経路上にある頂点のうち v 以外のものである。
影響を受ける頂点 u に対して S[u] の変化は S[u] -= S[v] となるので、ある経路に属する頂点に対する一律加算を実現したい。
ここで最初に用意した BIT を使う。
R[v] と v を結ぶ経路上にある頂点から S[v] を減算するには、頂点 0 と v の間にある点から S[v] を減算し、頂点 0 と R[v] の間にある点に S[v] を加算すればよい。
なお、この操作を行う前に multiset から値 S[R[v]] をひとつ削除し、操作が終わった後で値 S[R[v]] を追加する必要がある。ただし R[v] = v の場合は例外なので注意。
つぎに R を更新する方法を考える。R が変化するのは v の子孫たちである。
これは最初に pre-order で番号をふったのでひとつの区間で表される。v の子孫が範囲 [p..q] で表されるとする。
ここで注意するのは単に R[p..q] = v と更新してはいけないということである。
v の子孫たちのうち既に消された頂点がある場合、 R[p..q] はすべて v になるわけではないから、そこを除いて更新しなければならない。
そのために利用するのは「頂点 x が頂点 y の子孫の場合 x > y」という性質である。
すなわち、 R[p..q] は基本的には R[p..q] = R[v] となっているが、そうなっていない部分もある。
この性質から言えるのは、p ≦ x ≦ q かつ R[x] ≠ R[v] となる x があったとき、必ず R[x] > v が成立しているということである。
よって R を更新するには単なる代入ではなく max をとる、すなわち p ≦ x ≦ q なるすべての x について R[x] = max(R[x], v) を行う必要がある。
これは R を segment tree で実現しておくことで対数時間で行える。
最後に multiset を更新する。これは容易である。
v の直接の子 u に対し、まだ u が削除されていなければ S[u] を multiset に追加するだけでよい。
あとは答として multiset 中の最大の要素を返せばよい。
一回のクエリの計算量は O(deg(v) log N) である。(ただし deg(v) は v の次数)
deg(0) + deg(1) + ... + deg(N-1) = O(N) なので全体の計算量は O(N log N) 。