CODE FESTIVAL 2017 Elimination Tournament : D - Ancient Tree Record

解法はわかったけど間に合わず。
https://cf17-tournament-round1-open.contest.atcoder.jp/tasks/asaporo2_d

問題

N頂点の木を成す無向グラフがあり、各辺は正整数のコストが設定されているが、入力では明に与えられない。
各頂点iに関し、そこから各頂点へのコストの総和S[i]が与えられる。
各辺のコストを求めよ。

解法

頂点U-V間に辺があるとき、その間のコストを考えよう。

グラフのうちU側に近い頂点群を考え、Uからそれらへのコストの総和をAとする。またU側の頂点数をNuとおく。
同様にVからV側の頂点へのコストの総和をBとしよう。またU側の頂点数をNvとおく。
U-V間の辺のコストをwとすると
S[U] = A+B+Nu*w
S[V] = A+B+Nv*w
となるので、w = (S[U]-S[V])/(Nu-Nv)
となり、Nu!=Nvであれば実際にA,Bを求めることなくwを求められる。

Nu=Nvとなる辺はあっても1つなので、他の辺のコストを全部求めてしまおう。
そうすればA,Bが求められるのでwも求められる。

int N;
int U[101010],V[101010];
vector<int> E[101010];
map<pair<int,int>,int> M;
ll S[101010];
ll ret[101010];
int C[101010];
int D[101010];

int dfs(int cur,int pre,int d) {
	C[cur]=1;
	D[cur]=d;
	FORR(e,E[cur]) if(e!=pre) {
		C[cur]+=dfs(e,cur,d+1);
	}
	
	if(C[cur]!=N-C[cur] && pre!=-1) {
		ret[M[{cur,pre}]]=(S[cur]-S[pre])/(N-2*C[cur]);
	}
	return C[cur];
}

ll dfs2(int cur,int pre,ll sum) {
	ll tmp=sum;
	FORR(e,E[cur]) if(e!=pre) {
		tmp+=dfs2(e,cur,sum+ret[M[make_pair(cur,e)]]);
	}
	return tmp;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>U[i]>>V[i];
		U[i]--,V[i]--;
		E[U[i]].push_back(V[i]);
		E[V[i]].push_back(U[i]);
		M[{U[i],V[i]}]=M[{V[i],U[i]}]=i;
	}
	FOR(i,N) cin>>S[i];
	
	dfs(0,-1,0);
	
	FOR(i,N-1) {
		if(ret[i]==0) {
			ll tmp;
			if(D[U[i]]>D[V[i]]) {
				tmp=dfs2(U[i],-1,0);
				ret[i]=(S[U[i]]-tmp)/(N-C[U[i]]);
			}
			else {
				tmp=dfs2(V[i],-1,0);
				ret[i]=(S[V[i]]-tmp)/(N-C[V[i]]);
			}
			
		}
		cout<<ret[i]<<endl;
	}
	
}

まとめ

部分点にこだわらなければもう少し早く解けたかも。