Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【yukicode No.899 γatheree】オイラーツアー:BFSでたどると同じ階層のノードが連続になる

No.899 γatheree - yukicoder

問題

木(N=105)が与えられる。それぞれのノードにはAi匹の妖精がいる。

ノードkを指定すると、kから距離2にあるノードにいる妖精を集めることが出来る。

クエリ「ノードkを指定したあとに、ノードkにいる妖精の数を求める」

をQ(105)回答えよ。

方針

ライターの解法ブログを読み解きます。(低IQにつき、所要時間1時間)

BFS Euler Tour - niuez’s diary

木を何らかの方法で一次元にして、距離2以下のやつの集合を定数個くらいの集合に分割して、それらの和を足したのち、kに集約して、そいつらを0にするということが出来ればよい。区間updte区間sumの遅延セグツリー使うようにしたい。

もしノードkから距離1と距離2の範囲が配列上で連続になれば求まりそう。

f:id:akiradeveloper529:20191006162040j:plain

リンク先のコードは一回のBFSですべてを行っているが、わかりやすいように分解すると、

  1. BFS順にノードに番号を振ってしまう(id[v]とする)
  2. BFSでもDFSでも、各ノードの親を計算する
  3. BFSでもDFSでも、ノードを辿った順に、以下のコードを実行する
if p=par[v]が存在:
  chmin(L1[p], id[v])
  chmax(R1[p], id[v])
if pp=par[par[v]]が存在:
  chmin(L2[pp], id[v])
  chmax(R2[pp], id[v])

こうすると、すべてのノードについてL1,R1,L2,R2が計算される。

また、BFSで辿っていることにより、同じ階層のノードが連続になっている。