TopCoder SRM 581 Div1 Medium TreeUnion

問題

それぞれn頂点からなる木A, Bが与えられる。
この二つの木を次のようにしてつなぐ。

• 0, 1, ..., n - 1の順列をP[i]とする。
• A[i]とB[P[i]]の間に辺を張る。

出来たグラフに大きさKの単純閉路（同じ点を二度通らない閉路）はいくつできるか。
全ての順列が等しい確率で選ばれるとき、その期待値を求めよ。

制約条件

n≦300
3≦K≦7

方針

長さ3の閉路は絶対にできない。
Aの頂点→Bの頂点→Aの頂点→Bの頂点という風に、頂点を行き来するような閉路も、
A[i]とB[j]の間には高々1本しか辺がないので、K≦7では出来ない。

なので、Aのある線分(a, a')とBのある線分(b, b')をつないだような閉路だけを考えればよい。
Aの部分の長さは、1, 2, 3, ..., K - 3がありえる。

A, Bのそれぞれにおいて、頂点iから距離dのところにある頂点の個数をあらかじめ求めておく。
Aの線分(a, a')を一つ決めるとき、長さKの閉路がいくつできるか考える。

bを一つ決める。すると、b'の候補は、前計算により何個かわかっている。
a'のBにおけるペアが、b'の候補のどれかであれば長さKの閉路ができる。
この確率は、|b'| / (n - 1)
全てのbについて、この確率を1 / nして足し合わせればよい。
更にそれを、全てのaについて足し合わせる。

vector<vi> parse(const vector<string> &v){
	string s;
	rep(i, v.size()) s += v[i];
	stringstream ss(s);
	vi a;
	int x;
	while(ss >> x) a.pb(x);
	
	vector<vi> e(a.size() + 1);
	rep(i, a.size()){
		e[i + 1].pb(a[i]);
		e[a[i]].pb(i + 1);
	}
	return e;
}
void rec(const vector<vi> &e, int c, int p, int d, vi &res){
	if(d) rep(i, e[c].size()) if(e[c][i] != p){
		if(d == 1) res.pb(e[c][i]);
		else rec(e, e[c][i], c, d - 1, res);
	}
}
int enu(const vector<vi> &e, int s, int d){
	vi res;
	rec(e, s, s, d, res);
	return res.size();
}

class TreeUnion {
	public:
	double expectedCycles(vector <string> tree1, vector <string> tree2, int K) {
		vector<vi> a = parse(tree1), b = parse(tree2);
		int n = a.size();
		vector<vi> ps1(n, vi(K - 3)), ps2(n, vi(K - 3));
		for(int i = 1; i < K - 2; i++){
			rep(j, n) ps1[j][i - 1] = enu(a, j, i);
			rep(j, n) ps2[j][i - 1] = enu(b, j, i);
		}
		double ans = 0;
		rep(j, K - 3) rep(i, n) rep(k, n){
			ans += ps1[i][j] * 1.0 / n * ps2[k][K - 4 - j] / (n - 1);
		}
		return ans / 2;
	}
};