Codeforces #868 : Div2 F. Random Walk

こっちはどうにか。
https://codeforces.com/contest/1823/problem/F

問題

無向グラフと2点S,Tが与えられる。
点Sに置いた駒を、辺に沿って等確率でランダムで隣接点に動かすことを、駒が点Tに到達するまで繰り返す。
各点の訪問回数の期待値を求めよ。

解法

点SからDFSで処理する。
dp(v) := 各点vの訪問回数
とする。

まずSから見てTの奥にある点は訪問しない。
そうでない場合、dp(親頂点)÷(親頂点の辺の数)だけまずこの点を通る。
加えて、S-Tのパス上の点は、+1回必ず通る。

そこに、素直にTに向けて駒が動く確率は1/(点vの辺の数)なので、逆にdp(v)にはその逆数を掛けてやればよい。

int N,S,T;
vector<int> E[202020];
ll ret[202020];
const ll mo=998244353;
vector<int> D[2];

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;
}

//距離をDに入れるだけ

void dfs(int cur,int pre,vector<int>& D) {
	FORR(e,E[cur]) if(e!=pre) {
		D[e]=D[cur]+1;
		dfs(e,cur,D);
	}
}

void dfs2(int cur,int pre) {
	if(D[0][T]+D[1][cur]==D[0][cur]&&cur!=T) return;
	
	if(cur==T) {
		ret[cur]=1;
	}
	else {
		if(pre!=T) {
			ret[cur]=ret[pre]*modpow(E[pre].size())%mo;
		}
		if(D[0][cur]+D[1][cur]==D[0][T]) {
			ret[cur]++;
		}
		ret[cur]=ret[cur]*E[cur].size()%mo;
	}
	FORR(e,E[cur]) if(e!=pre) dfs2(e,cur);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S>>T;
	S--,T--;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	D[0].resize(N);
	dfs(S,S,D[0]);
	D[1].resize(N);
	dfs(T,T,D[1]);
	dfs2(T,T);
	FOR(i,N) cout<<ret[i]<<" ";
	cout<<endl;
}

まとめ

意外にシンプル。