Kodamanと愉快な仲間たち : Y - 待ち合わせ

これは先に解説見てしまったのでさっくりだった。
https://www.hackerrank.com/contests/kodamanwithothers/challenges/challenge-2162

問題

木を成す無向グラフが与えられる。
以下のクエリ(X,Y)に順次答えよ。

点Xに駒を置く。
その後、1秒毎に辺で隣接する点のいずれかに等確率で駒を動かす。
点Yに最初に到達するまでの時間の期待値を求めよ。

解法

証明は省略するが、点Aから隣接点Bに遷移するのにかかる期待値は、(BよりA側に近い頂点数*2)-1になるとのこと。
そこで、前処理として、各点でDFSで親方向に移動するのにかかる時間の期待値と親方向から降りてくる時間の期待値を求め、根から各頂点までそれぞれの累積和を取っておく。

あとは各クエリでX→LCA(X,Y)に上る時間をLCA(X,Y)→Yに降りる時間を前述の累積和から求めればよい。

int N,Q;
vector<int> E[200005];
int P[21][200005],D[200005];
int C[200005];
ll up[200005],down[200005];

void dfs(int cur) {
	C[cur]++;
	ITR(it,E[cur]) if(*it!=P[0][cur]) {
		D[*it]=D[cur]+1, P[0][*it]=cur, dfs(*it);
		C[cur]+=C[*it];
	}
	if(cur) {
		up[cur]=2*C[cur]-1;
		down[cur]=2*(N-C[cur])-1;
	}
}

void dfs2(int cur,int pre) {
	up[cur]+=up[pre];
	down[cur]+=down[pre];
	FORR(e,E[cur]) if(e!=pre) dfs2(e,cur);
}

int lca(int a,int b) {
	int ret=0,i,aa=a,bb=b;
	if(D[aa]>D[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb];
	return (aa==bb)?aa:P[0][aa];               // vertex
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0);
	dfs2(0,0);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
	
	while(Q--) {
		int U,V;
		cin>>U>>V;
		U--,V--;
		int lc=lca(U,V);
		cout<<(up[U]-up[lc]+down[V]-down[lc])<<endl;
	}
}

まとめ

最初これ最終問題だったのかな。