根付き木のハッシュ

りんごさんがちゃんとしたハッシュについての記事を書いてくれたのでそちらを推奨しておきます。
正当性を証明するにはユニークな多項式の形にしてmodを素数にしておけば、Schwartz–Zippel lemmaを使えて良いっぽい?
multisetのハッシュ、0になりやすいなぁと思ったけど0になる確率がat most n/modなのか。
記事での根付き木のハッシュの取り方を日本語にまとめておきます。

根付き木のハッシュ

まず、深さ i に対応する乱数 R_i を [0,mod) から取っておきます。
深さ i の頂点 v について、v 以下の部分木のハッシュは「(R_i + 子のハッシュ)の積」として計算します。
特に、葉のハッシュ値は 1 です。

詳細は実際に記事を読んで下さい。



僕は根付き木のハッシュを以下のように取っていました。
妥当性が証明できておらず、ほぼ嘘解法のようなものであるということを注意しておきます。

まず素数p,modを用意する。
ある頂点以下の部分木ハッシュ値は「p + 子のハッシュ値の二乗和」として下から計算していく。

いわゆる全方位木DPが簡単に書けて任意の根に対する任意の部分木のハッシュが計算できます。
(全方位木DPについてはそのうち書くかも?)

応用編としては、頂点にラベルがある場合は、ラベルに対する乱数的なハッシュをとり、それをpの代わりに使うと良いでしょう。

練習問題:http://codeforces.com/contest/763/problem/D
mod=1e9+7くらいでハッシュ取ると衝突するので、注意。この記事も参考に。