根付き木のハッシュ
木の高さd, 子のハッシュをc_1,c_2,..c_kとすると
元の木のハッシュは
x_d+Πc_i
で定義でき、x_0,x_1,..,x_dをランダムにすると、衝突確率は(d+1)/modで抑えられる。
noshi

AHU algorithmを使うと、各部分木に対して、0,1,2,..を辞書順で決定的にO(N)で割り当てられる。
1)高さiまでハッシュ列挙。
2)高さi+1の木の子のハッシュがソートされた状態で手に入っている。
3)高さi+1の木の子のハッシュをソートしたものを文字列と見なし、それのソート順をSA-ISで得る。
4)高さi+1の木に対してハッシュを順に割り当てる。
5)高さi+2の木の子であって、高さi+1であるもののハッシュを辞書順に順に割り当てる。

木T上で距離K離れている頂点同士を繋いだ別のグラフGを作った。Gの頂点0から到達できる頂点をO(NK)で列挙せよ。ABC414H

木A,Bが与えられる。Aは頂点ラベル付き、Bは頂点ラベルなし。Bに葉を一つ追加し、頂点ラベルを付けてAにする方法が何通りあるか。AtCoder

online dynamic connectivityのアルゴリズムを説明せよ。
Euler Tour Treeのアルゴリズムを説明せよ。