Similarity of Subtrees [JAG Practice Contest for ACM-ICPC Asia Regional 2016 : E]

問題

http://jag2016autumn.contest.atcoder.jp/tasks/icpc2016autumn_e

S(T,d)をある木Tの深さdであるノードの個数とする。
木Tと木T'が類似しているとは、全てのdにおいてS(T,d)=S(T',d)であること。

この時、ある木が与えられる。
この木の部分木のうち、類似している部分木の組合せは何個あるか。

1 <= N <= 10^5

考察

1. 木の同型性判定だ！
2. ググッてハッシュライブラリもってきて解く
3. サンプルが合わない
4. 木の同型性判定ではなく、深さが同じノードの数が同じなら良い
5. うーん

6. 木の問題なので、まずDFSかなという感じ
7. DFSをして、あるノードの部分木について、深さが同じ子ノードを数える
8. 子ノードの数えた結果から、親ノードを素早く数えたい
9. 木の同型性判定を考えてたおかげか、ローリングハッシュ的な手法が使えると天啓が下る

10. 一般的なローリングハッシュと同様、BaseとModを用意する
11. この時、ある部分木のハッシュを以下のように定める

ルートからの深さがiの個数をd[i]とすると、hash = sum{i=1,...} d[i] * Base^i

12. こうすると、親のノードの部分木のハッシュは以下のようになる

hash = sum{i=1,...,子ノード数} hash[i] * Base

13. Baseを一つかけることで、全ての深さを1つ下げることができるのでいい！
14. これで各ノードにおいてほぼ定数時間となるのでOK
15. あとは、ハッシュ値を数えて、組合せ計算するだけ

実装

http://jag2016autumn.contest.atcoder.jp/submissions/864160

#define BASE 1009
#define MOD 1000000007
typedef long long ll;
int N;
vector<int> E[101010];
//-----------------------------------------------------------------
map<ll, int> cnt;
ll dfs(int cur, int par) {
	ll hash = 1;
	for (int to : E[cur]) if (to != par) {
		ll h = dfs(to, cur);
		hash = (hash + h * BASE) % MOD;
	}
	cnt[hash]++;
	return hash;
}
//-----------------------------------------------------------------
int main() {
	cin >> N;
	rep(i, 0, N - 1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
 
		E[a].push_back(b);
		E[b].push_back(a);
	}
 
	dfs(0, -1);
 
	ll ans = 0;
	for (auto p : cnt) {
		ll c = p.second;
		ans += c * (c - 1) / 2;
	}
	cout << ans << endl;
}