根付き木のハッシュ

りんごさん方式の記事
正当性を証明するにはユニークな多項式の形にして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 + 子のハッシュ値の二乗和」として下から計算していく。

（適当なハッシュ関数 h を用意して、h(子の値)の和とかにしてもよいと思う。h(x)=x^2がうまく行きそうかつ簡単だったので二乗和にしたというだけ。）
（h(x)=hoge*xとかだと、深さの分布が同じで形が違う木を同一視してしまうのでダメ）
↑冷静に考えて、二乗和もあんまりよくないので（おまけ参照）、適当な良質かつ高速なハッシュ関数を使いましょう。
適当なハッシュ関数の例としては、Murmurハッシュとかを聞きました。
CF等のhackありのコンテストで使う場合、p にあたるものとか（あるなら）ハッシュ関数のseedとかをランダムに生成すると良さそう。

妥当性について

結局、根付き木のハッシュというのは、multisetのハッシュをどう取るかという話で、
「適当なハッシュ関数」が本当に良質なら、正当なハッシュの取り方だと思います。

備考

こっちの方式の売りなのですが、いわゆる全方位木DPが簡単に書けて任意の根に対する任意の部分木のハッシュが計算できます。
（全方位木DPについてはそのうち書くかも？）（←書いた。関連記事見て。）

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

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

おまけ

~~二乗和のハッシュの正当性の証明（または嘘である証明）お待ちしてます。~~
~~ちなみに４回くらい使いましたが全部ACしてます。~~
11頂点の木どうしで撃墜できました。 A - tree hash

撃墜例（ネタバレ？）

おまけ２

りんごさん式の方の全方位化ですが、

深さとハッシュ値のペアを計算していく
$R_i$ を外に出す（下記ツイート参照）

をすると、そこまで大変でもないかもしれません。
積なので左右からの累積積を持つか、logかけて逆元（0除算は確率的に無視して良い）でやるかしないといけない点はマイナスだけど、ハッシュ関数を用意しないで良い点はプラスという感じか。

Π(x_d + c_i) ではなく x_d + Πc_i にすると定数倍良好になると見込んでいる
多項式として異なる証明は x_(d-1) に対する因数分解から再帰的に従う
— 熨斗袋 (@noshi91) 2019年12月19日

※ この記事は2019/12/19にわりと加筆修正されました。