はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける木の同型判定問題まとめ

木の同型判定問題

メモ

ACM-ICPC 2016 国内予選 F: 文字解読

図形を木にした時に頂点数がそんなに多くならないので、多項式ベースのハッシュじゃなくても、文字列でハッシュを作っても全然間に合う。
https://kimiyuki.net/blog/2016/06/27/icpc-2016-domestic-f/
ここが詳しい。
図形を木に変換する問題としてカゴメカゴメがある(同型判定と関係無いけど)。
http://yukicoder.me/problems/no/348

HackerRank Tree Isomorphism

部分木のハッシュ値を一意にするために木の中心を探して、それを根としてハッシュを取る。
複数の中心がある場合はハッシュをとって小さい方を採用するとよい。

Codechef IOPC Techkriti 2012 - IIT Kanpur : Hardware upgrade

写像の組合せを問うものだが、木の同型判定ができればそれを利用して写像を作ることができる。
そのため、木の同型判定が大事になる。
以下の解説が分かりやすい。
http://d.hatena.ne.jp/komiyam/20120115/1326632089

TopCoderOpen 2015 Round2B Medium Balance

kmjpさんの解説がある。
http://kmjp.hatenablog.jp/entry/2015/06/21/0930
これも上の文字解読のように図形を木にして、同型判定する問題らしい。(やってない)

Codeforces Round #395 (Div. 1) D. Timofey and a flat tree

http://codeforces.com/contest/763/problem/D
この前出たやつ。ムズすぎて、まだ復習できてない。
考えても分からん。