便宜上 \(N\approx M\) の場合の計算量を示します。

永続セグメント木を用いて計算量を

• 前計算 \(O(N \log N)\)
• 質問ごとに \(O(\log N)\)

とすることができます。ただし、空間計算量が \(\Theta(N\log N)\) です。

永続セグメント木の実際の処理速度は通常のセグメント木等に比べて大幅に劣るため、このような方法では実質的な高速化は得られないことがよくあります。

パス \(S _ j-T _ j\) にある \(C _ i\) であって、全ての \(C _ i\) を昇順にソートしたとき \(k\) 番目までに入るものの和が \(Y _ i\) 以下か？ （JOI 解説スライドより）

という質問に対して、仮に

• 全ての \(C _ i\) を昇順にソートしたもののうち、パス \(S _ j-T _ j\) に含まれるもののみが有効な値となっている列を管理されているセグメント木

があれば、二分探索によって \(O(\log N)\) 時間で答えられます。

一方、永続化したセグメント木によって、各頂点 \(v\) について

• 全ての \(C _ i\) を昇順にソートしたもののうち、パス \(1-v\) に含まれるもののみが有効な値となっている列を管理されているセグメント木

を表すバージョンを構築できます。ここで \(v=S _ j,T _ j,\mathrm{median}(S _ j,T _ j, 1)\) のバージョンを参照すれば、上記の \(O(\log N)\) 時間の方法が実現できます。

（ \(\mathrm{median}(a,b,c)\) は頂点 \(c\) を根としたときの \(a\) , \(b\) の LCA を表します。）

解答例