概要
公式解説よりも計算量が良いので、書いておきます。
解法
消灯への対応
$v$ を出発した灯籠が、$w$ から先では消灯しているとします。このとき、
- $v$ から灯籠を $+1$ 個流す
- $w$ から灯籠を $-1$ 個流す
とすることにより、消灯しない灯籠を数え上げる問題に帰着できます。
$v, l$ をもとに $w$ を計算する必要がありますが、これはダブリングや HLD+segtree などによって $O(\log N)$ 時間で計算でき、この帰着は全体で $O(N + Q\log N)$ などの時間計算量で行えます。
矩形クエリへの帰着
回答クエリは次のように言い換えることができます。
- 頂点 $v$ の部分木内の灯籠のうち、根に到達する時刻が $t$ 以下であるものを数え上げよ
EulerTour をとって部分木を区間にすれば、矩形領域 $[l,r)\times [0,t]$ に追加された灯籠を数え上げる問題に帰着できます。
まとめ
$2$ 次元領域での点加算と矩形和のクエリを処理できれば問題を解くことができます。これは $2$ 次元 FenwickTree などでできます。
結局本問題は、全体として $O(N + Q\log N + Q\log^2Q)$ 時間で解くことができます。
