Submission #1857273

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
typedef pair<int, int> ii;
	
int n, pos, sz[N];
long long sum;
long long d[N];
long long a[N];
long long res[N];
vector<ii> G[N];

void dfs(int u, int p) {
	sz[u] = 1;
	for (auto v : G[u]) {
		if (v.first == p) continue; 
		dfs(v.first, u), sz[u] += sz[v.first];
		if (n != 2 * sz[v.first]) {
			res[v.second] = (a[v.first] - a[u]) / (n - 2 * sz[v.first]);
		}
		else pos = v.first;
	}
}

void redfs(int u, int p) {
	sum += d[u];
	for (auto v : G[u]) {
		if (v.first == p) continue;
		d[v.first] = d[u] + res[v.second], redfs(v.first, u);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back(ii(v, i));
		G[v].push_back(ii(u, i));
	}
	for (int i = 1; i <= n; ++i) cin >> a[i];
	dfs(1, 1), redfs(1, 1);
	for (int i = 1; i < n; ++i) {
		if (!res[i]) res[i] = (a[1] - sum) / sz[pos];
		cout << res[i] << '\n';
	}
}

Submission Info

Judge Result