Codeforces #395 Div1 D. Timofey and a flat tree

Cで手こずりすぎて本番時間切れ。どのみちハッシュ衝突でダメでした。
http://codeforces.com/contest/763/problem/D

問題

木を成す無向グラフが与えられる。
ある頂点を根とした場合を考える。
その状態で、各頂点におけるsubtreeにおいて同型なものを二重カウントしない場合、subtreeの種類が最多となるのはどの頂点を根とした場合か。

解法

各頂点において、その頂点を根としたときの各隣接点のSubtreeをハッシュ値で表現できるようにしよう。
あとはDFSで木を探索しつつ、同じハッシュを持つ木の数をmap等で増減させていき、異なるハッシュ値の数を求めていけばよい。
適当な頂点を根とすると、Subtreeのハッシュ値はDFSを2回使うテクで親方向も含めて求めることができる。

自分は各子頂点のsubtreeのハッシュをソートして重みづけ総和をとるハッシュ関数を利用した。
ほかの問題でも結構使っているのだが、この問題ではハッシュ衝突が頻出して結構苦戦してしまった。

木のハッシュについては以下の参考文献を参照。
根付き木のハッシュ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
rng_58's blog: Hashing and Probability of Collision

int N;
vector<int> E[101010];

ll V[101010];
vector<ll> H[101010],H2[101010];
pair<int,int> ret={-1,-1};
map<ll,int> hashes;

// T.size()+1要素を返す、先頭T.size()はその要素以外のhash、最後は全要素のハッシュ
vector<ll> tree_normalize(vector<ll> T) {
	static ll momo[2]={1000000007,1000000009};
	static vector<ll> prim = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79};
	vector<ll> R;
	sort(ALL(T));
	int id=0,i;
	
	ll a=1,b=1;
	R.push_back((a<<32)+b);
	FORR(r,T) {
		ll h=r>>32, l=r-(h<<32);
		(a+=h*prim[(id)%prim.size()])%=momo[0];
		(b+=l*prim[(id+2)%prim.size()])%=momo[1];
		id++;
		R.push_back((a<<32)+b);
	}
	a=b=0;
	for(i=T.size()-1;i>=1;i--) {
		ll h=T[i]>>32, l=T[i]-(h<<32);
		(a+=h*prim[(i-1)%prim.size()])%=momo[0];
		(b+=l*prim[(i+1)%prim.size()])%=momo[1];
		h=R[i-1]>>32, l=R[i-1]-(h<<32);
		a += h;
		b += l;
		R[i-1]=(a<<32)+b;
	}
	
	return R;
}

ll dfs(int cur,int pre) {
	FORR(e,E[cur]) if(e!=pre) H[cur].push_back(dfs(e,cur));
	V[cur]=tree_normalize(H[cur]).back();
	hashes[V[cur]]++;
	return V[cur];
}

void dfs2(int cur,int pre,ll par) {
	if(--hashes[V[cur]]==0) hashes.erase(V[cur]);
	if(pre!=-1) {
		hashes[par]++;
		H[cur].push_back(par);
	}
	sort(ALL(H[cur]));
	ret=max(ret,{hashes.size(),cur+1});
	
	int i;
	map<ll,ll> M;
	H2[cur]=tree_normalize(H[cur]);
	FOR(i,H[cur].size()) M[H[cur][i]]=H2[cur][i];
	
	FORR(e,E[cur]) if(e!=pre) dfs2(e,cur,M[V[e]]);
	
	if(pre!=-1 && --hashes[par]==0) hashes.erase(par);
	hashes[V[cur]]++;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,-1);
	dfs2(0,-1,0);
	cout<<ret.second<<endl;
}

まとめ

結構ハッシュ関数いじっても通らずびっくり。