<問題概要>
\( N \)頂点からなる木と、数列 \( P_i , A_i , B_i \) が与えられる。
木の各頂点には、カウンターがひとつずつ設置されている。全てのカウンターの初期値は \( 0 \) である。
この木に対して、以下のような操作を \( N \) 回行う。
- \( i \) 回目の操作は、頂点 \( P_i \) に対して行う。この頂点を \( V \) とする。
- まず、\( V \) を含む連結成分の全ての頂点 ( \( V \) 自身も含む ) にあるカウンターの値を、 \( A_i \) だけ増加させる。
- その後、\( V \) と \( V \) に繋がる辺全てをグラフから削除する。
各頂点 \( i \) について、カウンターが \( B_i \) 以上になるのは何回目の操作の後か求めよ。但し、そのようなことが起こらないなら \( -1 \) と出力せよ。
ファーストインプレッションは、(Union-Find+辺削除)ができる Dynamic Connectivity に、 ここ で示されている並列二分探索(パラレルバイナリサーチ) を使ってぐちゃぐちゃぐちゃぐちゃ… でも答えが出せはします。答えは出せますが恐らく定数の重い \( O(N \log^3 N) \) あたりになって、間に合わなくなります。閉店。(最近のCodeChefは想定で書いても結構TLギリギリになるケースも少なくなく、ちょっとでも遅い解法を書くとすぐTLEします…)
そこで、今から示すテクを使います。
今回は具体的に説明して、それを実装で一般化する方が分かりやすいので、具体例をもって説明します。面倒なので具体例の中では \( P=\{1,2,...,N\} \) 、すなわち頂点を番号順に消していくものとします。
図のような木を考えます。
そして、「頂点を \( 1,2,...,N \) の順で消す」を「頂点を \( N,(N-1),...,1 \) の順で出現させる」と捉え直します。ここまではよく見る典型。
まず、頂点 \(6\) を出現させます。
はい。
次に、頂点 \(5\) を出現させます。
ここで、 「 \( (5,6) \) 辺」というデータを記憶し、この頂点をひとつにまとめます。この時、出現順が遅い(元の問題で、先に消える)方をkeyとして残します。(これは経路圧縮のみを搭載したUFを使うと楽に実装可能です。)
ひとつにまとまりました。
この調子で次は頂点 \(4\) を出現させます。
本来あるのは \( (4,6) \) 辺ですが、その辺を \(5,6\) をひとつの頂点に潰した後では「 \( (4,5) \) 辺」として記録します。
続いて頂点 \(3\) が出現。
さらに頂点 \(2\) が出現。
「 \( (2,3) \) 辺」を記録、ひとつに潰す。
最後に頂点 \(1\) が出現。
例によって \( (1,6) \) 辺を「\( (1,4) \)辺」として、 \( (1,3) \) 辺を「\( (1,2) \)辺」として記録することになる。
操作終了。
では、ここで、記録した辺をもとに、「別の木」を再構築してみます。
この木は、 \(1\) を根とする根付き木です。
この木は、次のような特徴を持ちます。
「ある頂点 \(x\) は、 \(x\) から頂点 \(1\) に向かうパス上にある頂点たちから、根から順に操作の影響を受ける。」
例えば、頂点 \(5\) は頂点 \(1,4,5\) からこの順に影響を受けます。
要するに、この「別の木」を構築するということは、「操作の隷属関係を木にする」というイメージを持つとすんなり理解できると思います。
この「別の木」に問題が帰着出来れば、話は早いです。元の問題は、この「別の木」上で、
「「別の木」の \(1,x\) パス上の頂点に数 \(A_i\) が書いてある。このパス上を根から辿って、総和が \(B_i\) 以上になるのはどこか?」
これはダブリングを使えば上手くいきます(他にも方法があるかも)。詳しくは実装も参照してください。
このテク、どこかで見たことがあるけど名前がついてないか思い出せないか、どこで見たかも思い出せないのでせっかくなので記事にしてみました。
