CF1844G Tree Weights

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 $ .

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.

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.

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: