Submission #2193507

---

Source Code Expand

#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0;}
template<class T>bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0;}

using ll = long long;
using R = long double;
const R EPS = 1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r) {return (r > EPS) - (r < -EPS);}
inline R sq(R x) {return sqrt(max(x, 0.0L));}

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

// Problem Specific Parameter:

const int limit = 100010;
ll s[limit];

int a[limit], b[limit];
ll c[limit];

int asz[limit], bsz[limit];
vector<int> tree[limit];
int sz[limit], par[limit];

ll dist[limit];

int dfs(int v, int p) {
	par[v] = p;
	sz[v] = 1;
	for (auto &e : tree[v]) {
		const int v2 = v ^ a[e] ^ b[e];
		if (v2 == p) continue;
		sz[v] += dfs(v2, v);
	}
	return sz[v];
}

void calc(int v, int p, ll d) {
	dist[v] = d;
	for (auto &e : tree[v]) {
		const int v2 = v ^ a[e] ^ b[e];
		if (v2 == p) continue;
		calc(v2, v, d + c[e]);
	}
}

int main(void) {
	int n;
	cin >> n;

	rep(i, n - 1) {
		cin >> a[i] >> b[i];
		a[i]--, b[i]--;
		tree[a[i]].push_back(i);
		tree[b[i]].push_back(i);
	}

	rep(i, n) cin >> s[i];
	dfs(0, -1);

	rep(i, n - 1) {
		if (par[a[i]] == b[i]) {
			asz[i] = sz[a[i]];
			bsz[i] = n - asz[i];
		} else {
			bsz[i] = sz[b[i]];
			asz[i] = n - bsz[i];
		}

		if (asz[i] != bsz[i]) {
			c[i] = abs(s[a[i]] - s[b[i]]) / abs(asz[i] - bsz[i]);
		}
	}

	rep(i, n - 1) {
		if (asz[i] == bsz[i]) {
			calc(a[i], b[i], 0LL);
			calc(b[i], a[i], 0LL);
			ll cur = s[a[i]];
			rep(j, n) cur -= dist[j];
			c[i] = cur / (n / 2);
		}
	}


	rep(i, n - 1) cout << c[i] << endl;

	return 0;
}

Submission Info

Judge Result