Tree Weights
Contest: Codeforces Round 884 (Div. 1 + Div. 2)
Difficulty rating: 3000
Tags: bitmasks, constructive algorithms, data structures, dfs and similar, implementation, math, matrices, number theory, trees

You are given a tree with $$$n$$$ nodes labelled $$$1,2,\dots,n$$$. The $$$i$$$-th edge connects nodes $$$u_i$$$ and $$$v_i$$$ and has an unknown positive integer weight $$$w_i$$$. To help you figure out these weights, you are also given the distance $$$d_i$$$ between the nodes $$$i$$$ and $$$i+1$$$ for all $$$1 \le i \le n-1$$$ (the sum of the weights of the edges on the simple path between the nodes $$$i$$$ and $$$i+1$$$ in the tree).

Find the weight of each edge. If there are multiple solutions, print any of them. If there are no weights $$$w_i$$$ consistent with the information, print a single integer $$$-1$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

The $$$i$$$-th of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$u_i \ne v_i$$$).

The last line contains $$$n-1$$$ integers $$$d_1,\dots,d_{n-1}$$$ ($$$1 \le d_i \le 10^{12}$$$).

It is guaranteed that the given edges form a tree.

Output format:
If there is no solution, print a single integer $$$-1$$$. Otherwise, output $$$n-1$$$ lines containing the weights $$$w_1,\dots,w_{n-1}$$$.

If there are multiple solutions, print any of them.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In the first sample, the tree is as follows:

In the second sample, note that $$$w_2$$$ is not allowed to be $$$0$$$ because it must be a positive integer, so there is no solution.

In the third sample, the tree is as follows:

Example input:
5
1 2
1 3
2 4
2 5
31 41 59 26

Example output:
31
10
18
8

Example input:
3
1 2
1 3
18 18

Example output:
-1

Editorial:
Let $$$x_u$$$ be the sum of the weights of the edges on the path from node $$$1$$$ to node $$$u$$$. We know that $$$x_1 = 0$$$ and $$$x_i + x_{i+1} - 2x_{\text{lca}(i,i+1)} = d_i$$$ for all $$$1 \le i \le n-1$$$. This is a system of $$$n$$$ linear equations in $$$n$$$ variables.
As $$$x_u$$$ should be integers, let's first solve this system modulo $$$2$$$. The $$$2x_{\text{lca}(i,i+1)}$$$ term disappears, so we just have $$$x_{i+1} \equiv d_i - x_i \pmod 2$$$. Starting from $$$x_1 \equiv 0 \pmod 2$$$, this uniquely determines $$$x_2 \pmod 2$$$, then $$$x_3 \pmod 2$$$, and so on.
Now that we know $$$x_1,\dots,x_n \pmod 2$$$, write $$$x_u = 2x_u' + b_u$$$ where $$$b_u$$$ is the first bit of $$$x_u$$$. We can rewrite our system of equations as
$$$$$$(2x_i'+b_i) + (2x_{i+1}'+b_{i+1}) - 2(2x_{\text{lca}(i,i+1)}'+b_{\text{lca}(i,i+1)}) = d_i$$$$$$ $$$$$$\iff x_i' + x_{i+1}' - 2x_{\text{lca}(i,i+1)}' = \frac{1}{2}\left(d_i-b_i-b_{i+1}+2b_{\text{lca}(i,i+1)}\right)$$$$$$
which has the same form as the original system. Thus we can repeat this process to find $$$x_u' \pmod 2$$$ (giving $$$x_u \pmod 4$$$), then $$$x_u \pmod 8$$$, and so on. Note that each bit of $$$x_u$$$ is uniquely determined.
If a solution exists, it satisfies $$$0 \le x_u \le n \cdot \max d_i \le 10^{17}$$$ for all $$$u$$$, so it suffices to repeat this process until we have found the first $$$57$$$ bits of $$$x_u$$$. Finally, we check that these $$$57$$$ bits correspond to a valid solution where all the original weights are positive.
The time complexity is $$$\mathcal{O}(n(\log n + \log \max d_i))$$$, if the $$$\text{lca}(i,i+1)$$$ are precomputed.
Remark: This idea is related to the method of Hensel Lifting.