AtCoder ARC #150 : D - Removing Gacha

まぁまぁ良かった回。
https://atcoder.jp/contests/arc150/tasks/arc150_d

問題

根付き木が与えられる。
初期状態で各頂点は白である。

ある点が悪いとは、その点から根までのパス上に、白い頂点が1個でもある状態である。

全点が黒になるまで、以下を繰り返す。

• 悪い点のうち1つを等確率で選び、その点を黒で上書きする。

全点が黒くなるまでの操作回数の期待値を求めよ。

解法

深さDの点が良くなるまでに必要な操作回数の期待値をf(D)とする。
そうすれば各点vに対しf(depth(v))の総和が解となる。

f(D)は、D+1個のカードに対するコンプガチャをするうえで、ある1枚のカードを選ぶ回数の期待値なので、1+1/2+1/3+....+1/(D+1)となる。

const ll mo=998244353;
int N;
int P[202020];
vector<int> E[202020];
int C[202020];
ll dp[202020];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

int dfs(int cur) {
	C[cur]=1;
	FORR(e,E[cur]) {
		C[cur]+=dfs(e);
	}
	
	dp[cur]=modpow(C[cur]);
	FORR(e,E[cur]) {
		dp[cur]+=dp[e];
	}
	dp[cur]%=mo;
	
	
	return C[cur];
}

ll F[202020];
int D[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=201010;i++) {
		(F[i]=F[i-1]+modpow(i))%=mo;
	}
	ll ret=0;
	D[0]=1;
	cin>>N;
	for(i=1;i<=N;i++) {
		cin>>P[i];
		P[i]--;
		D[i]=D[P[i]]+1;
		ret+=F[D[i]];
	}
	cout<<ret%mo<<endl;
}

まとめ

本番よくこれすんなり解いたな。
実験ゲーしたんだっけかかな。