SRM 660 Div1 Medium Privateparty

各頂点に対して独立に期待値を求める。
有向グラフにして考える。
開始頂点を w とする。
頂点 u から v に辺が張られているとする。u が先に招待される場合は、自明に u は招待される。
v が先に招待される場合は、v の先の頂点まで見る必要があるので DFS を行う。
開始頂点 w から u の距離が k のとき、前者の係数は、1-1/(k+2), 後者の係数は、 1/(k+2) となる。(後者の場合は、w から u までのパスに含まれるすべての頂点より先に招待される必要があり、w から v までのパスに含まれる頂点数が k+2 個であることから分かる)

一見閉路があるように見えるが、1週してきた場合は、頂点が無い場合と同一視できる。

#define N 100
bool used[N];
vector<int> a;

class Privateparty {
	public:
	double dfs(int u, int k){
		used[u] = true;
		if(used[a[u]]){
			used[u] = false;
			return 1.0;
		}
		double y = dfs(a[u], k+1);
		used[u] = false;
		return (k-1.0)/k+(1.0)/k*(1-y);
	}
	double getexp(vector <int> a_) {
	a=a_;
		int n = a.size();
		double res = 0.0;
		rep(i, n) res += dfs(i, 2);
		return res;
	}
};