読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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

http://codeforces.com/contest/763/problem/D

問題概要

木が与えられる。ある頂点を根としてみたとき n 個の部分木がある。もっとも部分木の形状の種類が多くなるような根の選び方を求めよ。部分木の形状が等しい、というのは根付き木として同型であるということである。

解法

以下を大いに参考にする。

rng-58.blogspot.jp

snuke.hatenablog.com

基本的にハッシュなんて適当に作っても(悪意がなければ)衝突しないのだが、ちゃんとしたハッシュというのがあるらしいので利用した。

基本的に全方位木 DP である。高さが絡むおかげで実装が面倒になっている。まあ、そんなに面倒かといわれると面倒でもないのだが…。

逆元を使わない実装にしたけど、逆元が使えない確率は小さいので使ってもいいと思う。