CSAcademy Round #62 : E. Trees Partition

解法はすぐ思いついたのにね。
https://csacademy.com/contest/round-62/scoreboard/

問題

1番の頂点を根とする1～Nのラベル付き頂点の根付き木が２つ与えられる。
両グラフに対し１辺ずつ選び、それぞれ切断する。
両グラフは２つに分断されるが、それぞれに含まれる頂点ラベル集合が一致するような辺の組み合わせは何通りか。

解法

根付き木を辺で切り離すので、根を含まない方について、ラベルの集合をハッシュ値で数え上げよう。
自分はハッシュ値として頂点番号iに関し2^iの総和をハッシュ値とした。
ただしmod 10^9+7だとまだ衝突するので、mod 10^9+7とmod 10^9+9の２つのハッシュ値を用いた。

int N;
map<pair<ll,ll>,ll> M;
vector<int> E[2][303030];

ll p2[2][303030];
ll mo[2]={1000000007,1000000009};
ll dp[2][303030];
ll ret;

void dfs(int cur,int pre) {
	dp[0][cur]=p2[0][cur];
	dp[1][cur]=p2[1][cur];
	FORR(e,E[0][cur]) if(e!=pre) {
		dfs(e,cur);
		(dp[0][cur]+=dp[0][e])%=mo[0];
		(dp[1][cur]+=dp[1][e])%=mo[1];
	}
	if(cur!=1) M[{dp[0][cur],dp[1][cur]}]++;
}
void dfs2(int cur,int pre) {
	dp[0][cur]=p2[0][cur];
	dp[1][cur]=p2[1][cur];
	FORR(e,E[1][cur]) if(e!=pre) {
		dfs2(e,cur);
		(dp[0][cur]+=dp[0][e])%=mo[0];
		(dp[1][cur]+=dp[1][e])%=mo[1];
	}
	if(cur!=1) ret+=M[{dp[0][cur],dp[1][cur]}];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	p2[0][0]=p2[1][0]=1;
	FOR(i,N) {
		p2[0][i+1]=p2[0][i]*2%mo[0];
		p2[1][i+1]=p2[1][i]*2%mo[1];
	}
	
	for(i=2;i<=N;i++) {
		cin>>x;
		E[0][x].push_back(i);
	}
	for(i=2;i<=N;i++) {
		cin>>x;
		E[1][x].push_back(i);
	}
	dfs(1,-1);
	ZERO(dp);
	dfs2(1,-1);
	
	cout<<ret<<endl;
	
	
}

まとめ

想定解もハッシュだけど、Editorialには別の人がdeterministicな方法をコメントしている。