概要
解説がなさそうだったので書きますシリーズ。
ありましたが、別方針だったので残しておきます。
解法
適当な根を固定して、根付き木として扱います。事前に各クエリに対する LCA を計算しておきます。
Euler Tour + Fenwick Tree
Euler Tour の基礎が分からない場合、私の記事 も参考になると思います。
Euler Tour と Fenwick Tree を使うことで、次のクエリ処理が、どちらもクエリあたり $O(\log N)$ 時間で行えます。
- 頂点 $v$ に $x$ を加算する
- $vw$ パス上の頂点に加算されている値の総和を求める
$vw$ パスに関する計算は、根から $v, w, \text{LCA}(v, w)$ 等へのパスに関する計算の足し引きで行えることに注意しましょう。
並列二分探索
頂点の重みを昇順にソートして、$x_1, x_2, \ldots$ としましょう。各クエリに対して「答は $x_k$ 以下である」という判定問題を考えます。この判定問題は、以下のように言い換えられます。
- 頂点 $x_1, \ldots, x_k$ を持つ頂点に $1$ を加算する
- パス $vw$ 上の頂点に加算されている値の総和が $l$ 以下であるかを判定せよ
この判定問題は、Euler Tour + Fenwick Tree で解けるのでした。
この判定問題を並列二分探索の形で行うことで、全体として $O((N+Q)\log^2N)$ 時間で本問題を解くことができます。
