yukicoder No.778 クリスマスツリー
お題箱より。
解法
飾りを頂点0を根とする根付き木とみなします。言葉を言い換えると、求めるものは以下の2条件を満たすペア の個数です。
- 頂点
が頂点
の先祖である。
- 頂点番号について、
である。
ここでの「先祖」は、ある頂点の親、その親、その親…を根まで辿った頂点全てを指します。また、先祖と逆の関係にあるものを「子孫」と表現することにします。
つまり「位置関係（親子関係）」と「頂点番号の大小関係」の2つが条件になっています。このような問題では、片方の条件が扱いやすいような探索順番で頂点を見ていきながら、データ構造などを用いてもう片方の条件を満たすものを効率的に数える、という方法が有効であることが多いです。
そのような解法を2つ紹介します。
解法1
解法1では、親子関係を扱いやすい探索順で探索していくことを考えましょう。深さ優先探索で頂点を1つずつ見ていくことを考えます。
木の深さ優先探索では「今見ている頂点の先祖にある頂点たち」の集合を管理しながら探索することができます。具体的には頂点 を訪れたとき、以下のような手順で処理します。
- まずは、頂点
- 先祖たち集合の中に頂点
- 頂点
- 子を全て処理し終わって頂点
先祖たち集合として set を利用したC++の実装イメージは以下です。処理全体で同じものを使うので、グローバル変数にするか参照渡しで渡してあげてください。
set<int> ancestors; void dfs(int i){ ans += <iより番号の小さい先祖の個数>; ancestors.insert(i); for(int j : child[i]) dfs(j); ancestors.erase(i); return; }
あとは、各頂点 を訪れた時に「
より番号の小さい先祖の個数」を効率的に求めることが必要です。これはデータ構造を用いましょう。上記のコード中で
setを使っている代わりに、頂点番号をインデックスとしたBITやセグメント木を用いればよいです。
解法1 ACコード
#353465 No.778 クリスマスツリー - yukicoder
これは
- 親子関係を扱いやすい探索順にして、
- 頂点番号の大小関係をデータ構造で処理する
という解法でした。個人的にはこちらの解法が解きやすくてオススメです。
解法2
次に公式解法のほうです。こちらは解法1とは逆で、
- 頂点番号の大小関係を扱いやすい探索順にして、
- 親子関係をデータ構造で処理する
というものになっています。
頂点番号を大きい方から見ていくことを考えます。そうすると、ある頂点 を見ているときに数えるべきものは、
- 既に見た頂点であって、頂点
となります。解法1では数える条件が「頂点番号が より小さい」だったので区間和が使えましたが、「子孫である」という条件はどう扱いましょう？
ここで使えるのがオイラーツアーというテクニックです。これは根付き木に対して「DFSで訪れた頂点の順番を、行き帰り含めて全て並べた数列」を求めたものです。
英語ページですが、図があったほうが良いと思ったので参考としてこちらを紹介します。
Euler Tour of Tree - GeeksforGeeks
このオイラーツアーの数列において、部分木（ある頂点自身とその子孫からなる木）は連続した1つの区間を構成しています。つまりオイラーツアーの数列に対応したBITを作ると、「頂点 の子孫であるものの個数」は区間和として効率的に計算することができます。
つまり頂点番号を大きい方から見ていきながら、それぞれの頂点 を見る時に
のように処理することで解けます。一般にオイラーツアーでは1つの頂点のインデックスが複数個入るので、値を足す際には注意してください。この問題の場合はどこでもいいので1箇所に足せば大丈夫です。
