Submission #2123965

---

Source Code Expand

#include <iostream>
#include <vector>
#include <utility>
#define llint long long

using namespace std;
typedef pair<llint, llint> P;

llint N;
llint s[100005];
vector<P> G[100005];
llint ans[100005];
llint centi, centa, centb;

llint dfs(int v, int prev)
{
	llint ret = 0, res, d1, d2;
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i].first == prev) continue;
		res = dfs(G[v][i].first, v);
		ret += res;
		if(N % 2 == 0 && res == N/2){
			centi = G[v][i].second;
			centa = v;
			centb = G[v][i].first;
			continue;
		}
		ans[G[v][i].second] = (s[v] - s[G[v][i].first]) / (2*res - N);
	}
	return ret + 1;
}

P dfs2(int v, int prev)
{
	P ret = make_pair(0, 0), res;
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i].first == prev) continue;
		res = dfs2(G[v][i].first, v);
		ret.first += res.first + res.second * ans[G[v][i].second];
		ret.second += res.second;
	}
	ret.second++; 
	return ret;
}

int main(void)
{
	cin >> N;
	int a, b;
	for(int i = 1; i <= N-1; i++){
		cin >> a >> b;
		G[a].push_back(make_pair(b, i));
		G[b].push_back(make_pair(a, i));
	}
	for(int i = 1; i <= N; i++) cin >> s[i];
	
	dfs(1, -1);
	if(centi != 0){
		llint s1 = dfs2(centa, centb).first;
		llint s2 = dfs2(centb, centa).first;
		ans[centi] = (s[centa] - (s1+s2)) / (N / 2);
	}
	
	for(int i = 1; i <= N-1; i++){
		cout << ans[i] << endl;
	}
	return 0;
}

Submission Info

Judge Result