出题人脑洞真大……
设 \(x_i\) 为 \(i\) 到 \(1\) 的距离。我们知道 \(\forall i \in [1, n - 1], x_i + x_{i + 1} - 2 x_{\operatorname{lca}(i, i + 1)} = d_i\)。发现每个方程有 \(3\) 个未知数，很烦。能不能消掉一个？
发现若整个方程模 \(2\)，\(x_{i + 1} \equiv d_i - x_i \pmod 2\)。因此可以得知所有 \(x_i\) 二进制下最低位。再递归处理接下来的位。于是我们发现 \(x_i\) 若有解则一定是唯一确定的。
预处理出 \(b_i = \operatorname{lca}(i, i + 1)\)，时间复杂度 \(O(n (\log n + \log V))\)。
code
// Problem: G. Tree Weights
// Contest: Codeforces - Codeforces Round 884 (Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1844/problem/G
// Memory Limit: 256 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 100100;
ll n, a[maxn], b[maxn], c[maxn], d[maxn], ans[maxn];
vector<pii> G[maxn];
int fa[maxn], sz[maxn], son[maxn], dep[maxn], top[maxn];
bool vis[maxn];
int dfs(int u, int f, int d) {
fa[u] = f;
sz[u] = 1;
dep[u] = d;
int maxson = -1;
for (pii p : G[u]) {
int v = p.fst;
if (v == f) {
continue;
}
sz[u] += dfs(v, u, d + 1);
if (sz[v] > maxson) {
son[u] = v;
maxson = sz[v];
}
}
return sz[u];
}
void dfs2(int u, int tp) {
top[u] = tp;
vis[u] = 1;
if (!son[u]) {
return;
}
dfs2(son[u], tp);
for (pii p : G[u]) {
int v = p.fst;
if (!vis[v]) {
dfs2(v, v);
}
}
}
inline int qlca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
x = fa[top[x]];
}
if (dep[x] > dep[y]) {
swap(x, y);
}
return x;
}
void dfs3(int u, int fa) {
for (pii p : G[u]) {
int v = p.fst, id = p.scd;
if (v == fa) {
continue;
}
ans[id] = a[v] - a[u];
if (ans[id] <= 0) {
puts("-1");
exit(0);
}
dfs3(v, u);
}
}
void solve() {
scanf("%lld", &n);
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
G[u].pb(v, i);
G[v].pb(u, i);
}
for (int i = 1; i < n; ++i) {
scanf("%lld", &d[i]);
}
dfs(1, -1, 1);
dfs2(1, 1);
for (int i = 1; i < n; ++i) {
b[i] = qlca(i, i + 1);
}
for (int k = 0; k < 60; ++k) {
for (int i = 1; i < n; ++i) {
ll t = d[i] - a[i] - a[i + 1] + a[b[i]] * 2;
if (t < 0 || t % (1LL << k)) {
puts("-1");
return;
}
t /= (1LL << k);
t = (t % 2 + 2) % 2;
c[i + 1] = ((t - c[i]) % 2 + 2) % 2;
}
for (int i = 2; i <= n; ++i) {
if (c[i]) {
a[i] |= (1LL << k);
}
}
}
dfs3(1, -1);
for (int i = 1; i < n; ++i) {
printf("%lld\n", ans[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}