TopCoder SRM 581 Div1 Medium TreeUnion

問題

N頂点からなる木A, Bがそれぞれ与えられる。
A, Bを次のようにしてつなぐ。
長さNの順列を等確率にランダムで一つ取り、これをP[i]とする。

Aのi番目の頂点とBのP[i]番目の頂点を辺で結ぶ。

こうしてできたグラフに、長さがちょうどkの単純閉路がいくつできるか、
その期待値を求めよ。

制約条件

N≦50
長さkの単純閉路とは、グラフ上にk個の異なる頂点v0, v1, ..., vk-1であって、
v0とv1, v1とv2, ..., vk-2とvk-1, vk-1とv0がそれぞれ辺で結ばれているようなもの。

方針

ソースコード

int n1, n2;
int d1[310][310], d2[310][310];
vector<vi> t1, t2;

vector<vi> parse(vector<string> s, int &n, int d[310][310]){
	
	string t;
	rep(i, s.size()) t += s[i];
	stringstream ss(t);
	
	int k;
	vi v;
	while(ss >> k) v.pb(k);
	
	n = v.size() + 1;
	vector<vi> e(n);
	
	rep(i, n) rep(j, n) d[i][j] = i == j ? 0 : inf;
	rep(i, v.size()){
		e[i + 1].pb(v[i]);
		e[v[i]].pb(i + 1);
		d[i + 1][v[i]] = d[v[i]][i + 1] = 1;
	}
	
	rep(k, n) rep(i, n) rep(j, n) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	return e;
}

class TreeUnion {
	public:
	double expectedCycles(vector <string> tree1, vector <string> tree2, int K) {
		t1 = parse(tree1, n1, d1);
		t2 = parse(tree2, n2, d2);
		
		int cnt[310] = {};
		double ans = 0;
		
		rep(i, n2) rep(j, n2) if(i != j) cnt[d2[i][j]]++;
		
		rep(i, n1) rep(j, i){
			int r = K - d1[i][j] - 2;
			if(r <= 0 || r > 300) continue;
			
			ans += cnt[r] * 1.0 / n2 / (n2 - 1);
		}
		return ans;
	}
};