Good Bye 2014 : D. New Year Santa Network

ちょっとややこしいが、本番1発AC出来て良かった。
http://codeforces.com/contest/500/problem/D

問題

(N-1)本の移動コストL[i]付無向辺で連結されたN頂点のグラフがある。

ここで、2頂点u,vの最短移動コストをd(u,v)と表記する。
N頂点中、異なる3点d1,d2,d3が等確率で選択されるとき、d(d1,d2)+d(d2,d3)+d(d3,d1)の期待値を求めたい。

ただし、ここでQ個のクエリが与えられる。
各クエリは、ある１本の辺に対しコストをW[i]に減少するものである。
クエリ実行後の上記期待値を求めよ。

解法

各辺のコストが最終的な期待値にどの位影響するか考えると良い。
d(d1,d2)+d(d2,d3)+d(d3,d1)の値に辺のコストが影響するのは、d1,d2,d3の３点が辺の両側に1点と2点または2点と1点に分かれる場合であり、d(d1,d2)+d(d2,d3)+d(d3,d1)の値にコストが２回加算される。

よってまず、DFSで各辺において辺の両側に何個の頂点があるか計算する。
例えば両側にx個・(N-x)個とすると、この辺のコストL[i]が最終的な期待値に与える影響は
である。

よってまず各辺における上記式の和を取り、後は各クエリ毎に辺のコストがL[i]→W[i]と減少するごとに上記式の分減少させていけば良い。

int N,Q;
ll P[4][1020000];

int A[102000],B[102000],L[102000],NN[102000];
vector<pair<int,int> > E[102000];
vector<int> num[102000];
double tot;

int dfs(int cur,int pre) {
	int i,j=-1;
	int n=1;
	num[cur].resize(E[cur].size());
	
	FOR(i,E[cur].size()) {
		int tar=E[cur][i].first;
		if(pre==tar) j=i;
		else {
			n+=num[cur][i]=dfs(tar,cur);
			NN[E[cur][i].second]=num[cur][i];
		}
	}
	if(j>=0) {
		num[cur][j]=N-n;
		NN[E[cur][j].second]=N-n;
	}
	return n;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	
	FOR(i,102000) {
		P[0][i]=1;
		P[1][i]=i;
		P[2][i]=1LL*i*(i-1)/2;
		P[3][i]=1LL*i*(i-1)*(i-2)/6;
	}
	
	FOR(i,N-1) {
		cin>>A[i]>>B[i]>>L[i];
		A[i]--,B[i]--;
		E[A[i]].push_back(make_pair(B[i],i));
		E[B[i]].push_back(make_pair(A[i],i));
	}
	dfs(0,-1);
	
	double tot=0;
	FOR(i,N-1) {
		ll n=NN[i];
		tot+=L[i]*1.0*(P[1][n]*P[2][N-n]*2+P[2][n]*P[1][N-n]*2);
	}
	cin>>Q;
	while(Q--) {
		cin>>x>>y;
		x--;
		ll n=NN[x];
		tot-=(L[x]-y)*1.0*(P[1][n]*P[2][N-n]*2+P[2][n]*P[1][N-n]*2);
		L[x]=y;
		_P("%.12lf\n",tot/P[3][N]);
	}
}

まとめ

２点じゃなくて３点なのでちょっとややこしいね。