Codeforces #343 Div2. E. Famil Door and Roads

さっくり解けて良かった。
http://codeforces.com/contest/629/problem/E

問題

木を成すグラフが与えられる。
これらに対し、以下のクエリM個に順次答えよ。

各クエリは頂点対(u,v)からなる。
木に対し、ある２頂点間に辺を追加したとする。
元の木ではu→vの経路は１つしかないが、辺を追加したことで２つになり、u→v→uに至る閉路ができる可能性がある。
辺を追加する２頂点が等確率で選択されるとき、閉路が出来るケースにおいて、その閉路長の平均値を求めよ。

解法

まずLCAを求められるようにしよう。

簡単なケースは、LCA(u,v)がu,vと一致しない場合である。
この場合、追加した辺がuのsubtree中の点と、vのsubtree中の点を結ぶなら、新たに閉路を作ることになる。
そこで、各頂点pに対し、subtreeの頂点数V(p)と、subtreeの各頂点に至るまでの距離の総和S(p)をDFSで求めよう。
pからsubtreeのどこかの頂点に致す経路の平均帳はS(p)/V(p)となる。
よって、求める解は以下の和である。

• 元々のu→LCA(u,v)→vの距離
• 追加する辺の距離1
• uからsubtreeのどこかの点への平均距離S(u)/V(u)
• vからsubtreeのどこかの点への平均距離S(v)/V(v)

u,vのどちらかがLCA(u,v)と一致する場合は注意が必要。
例えばu=LCA(u,v)の場合、追加する辺の一端はvのsubtreeで良いが、u側は「全頂点のうち、u→v側に向けて１つ進んだ子頂点のsubtreeを除いた点」のどれかを選ぶ。
上記のような点の平均距離を求めるため、DFSを２回行って、各頂点から全頂点への平均距離を求めておこう。
後は以下の和を求めればよい。

• 元々のu→vの距離
• 追加する辺の距離1
• vからsubtreeのどこかの点への平均距離S(v)/V(v)
• uから全頂点のうち、u→v側に向けて１つ進んだ子頂点のsubtreeを除いた点への平均距離

int N,M;
vector<int> E[101010];
int P[21][200005],D[200005];

int sub_v[101010];
ll sub_d[101010];
ll par_d[101010];

void dfs(int cur) {
	sub_v[cur]=1;
	ITR(it,E[cur]) if(*it!=P[0][cur]) {
		D[*it]=D[cur]+1;
		P[0][*it]=cur;
		dfs(*it);
		sub_v[cur]+=sub_v[*it];
		sub_d[cur]+=sub_d[*it]+sub_v[*it];
	}
}

void dfs2(int cur,ll p) {
	par_d[cur]=p;
	ll tot=p+sub_d[cur];
	ITR(it,E[cur]) if(*it!=P[0][cur]) {
		ll p2=tot-(sub_d[*it]+sub_v[*it])+(N-sub_v[*it]);
		dfs2(*it,p2);
	}
}

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
}

int getpar(int cur,int up) {
	int i;
	FOR(i,20) if(up&(1<<i)) cur=P[i][cur];
	return cur;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	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(M--) {
		cin>>x>>y;
		x--,y--;
		if(D[x]>D[y]) swap(x,y);
		int lc=lca(x,y);
		
		ll base=(D[x]-D[lc])+(D[y]-D[lc])+1;
		double xs,ys=sub_d[y]*1.0/sub_v[y];
		if(x==lc) {
			int yp=getpar(y,D[y]-D[x]-1);
			xs=(par_d[x]+sub_d[x]-(sub_d[yp]+sub_v[yp]))*1.0/(N-sub_v[yp]);
		}
		else {
			xs=sub_d[x]*1.0/sub_v[x];
		}
		_P("%.12lf\n",base+xs+ys);
	}
}

まとめ

u,vの片方がLCAとなるケースをうまく解けて良かった。