Codeforces Round #629 (Div. 3) - E. Tree Queries
概要
サイズNの木が与えられる。根を頂点1とする。
次のようなM個のqueryに答えよ。
- k個の頂点を与える。頂点1からある頂点vへ行くパスからの距離が、k個の頂点すべてに対して、1以下となるvが存在するのならばYES、ないのならNOと答えよ。
制約： 1 <= N, M <= 2 * 10^5, M個のqueryの頂点の総和は2 * 10^5以下
ACするまで
1. LCAでできるのかなぁ・・・。でもE問題だしなくてもできそう
2. ひとまず、頂点1と、頂点1から距離1の頂点たちは除外できる。(必ず距離1なので)
3. いい感じに、入力された頂点が、頂点1からの枝分かれとかで同じところに収まればいい。でもきれいな実装や判定が思いつかない。
4. 解説AC。LCAを使う方も使わないほうもあった。
考察
LCA
木についての有名なクエリ問題として、Lowest Common Ancestorつまり根が決まったときの2点の最近共通祖先を求める問題がある。
まず、クエリの中で、与えられた頂点のうち、メインパスにするべき頂点vは、与えられた頂点のうちの最深のものでなければいけない。
あとは、あらかじめ頂点ごとの深さを求めておき、
頂点vとほかの頂点とのLCAを求めて、これとほかの頂点との距離が、メインパスからの距離となる。
これが2以上ならば、これは解なし、NOという答えとなる。
DFSで工夫する
Now there are two ways: write some LCA algorithms and other hard stuff which is unnecessary in this problem or write about 15 lines of code and solve the problem. (by writer's turorial)
https://codeforces.com/blog/entry/75246
意訳： 今2つの選択がある。1つにはLCAやそれに準ずる面倒な、しかしながらこの問題では必要ではないアルゴリズムを用意すること。もう1つは15行ばかしのコードを書いて、ACしちゃうことだ。
これは2つテクニックを知っていれば、LCAを持ち出すまでもなくACできる。
メインパスの考えはLCA解と同じ。最深の頂点まで行くパスとの距離が1以内か？を計算する。
まず、次図のように、それぞれの頂点に対して、1つの閉区間を持たせる。
上図の頂点9において、区間が[9, 9]です。(書き忘れた)
このように、DFSをするだけで、「pを頂点とする部分木にqが含まれてるか？」を求められるのである。
しかし、ここで困ったのが1つ。すべてがパスの上に並んでいる、というのならば区間比較で終わるが、メインパスからの距離が1であるという条件が地味に厄介。
しかし、これはつぎのように言い換えればよい。
もともとメインパス上にあるもので、頂点1以外ならば、親も必ずメインパス上にある。
もともとないものなら、距離1であるためには、親は必ずメインパスにないといけないからである。
これらの考えでLCAを持ち出さずに実装できる。
でもライブラリを使ってペッ！ｗのLCAの方が15行タイピングより早いだろという意見を俺は否定できない。
一言
この回のコドフォ、大敗すぎて出ていたらレートがめちゃくちゃ下がっていただろうなぁ。3完だし。
