木の重心を \(c\) とし，木を \(c\) を根とする根付き木として考えます．また，頂点 \(v\) の親を \(p_v\) とします．

このとき，各頂点 \(v\) について， \(v\) の部分木に含まれる頂点の数は，それ以外の頂点の数より常に少なくなります．よって，辺 \((v,p_v)\) について操作を行ったとき， \(v\) の部分木に含まれない頂点すべてに辺の番号 (\(i\) とする) が加算されます．

これは， \(v\) の部分木に含まれる頂点全てに \(-i\) を加算したあと，全体に \(i\) を加算する，と言い換えることができます．ここで，全体に加算される値の総和は \(1+2+\cdots+(N-1)\) なので，あとでまとめて行います．

各頂点について自身に加算される値を公式解説と同様に求めれば， \(O(N)\) で実行できます．