410797: GYM104114 M Mousetrap

Jerry has a network of $$$n$$$ chambers connected by $$$n-1$$$ bi-directional tubes, such that any two chambers are (directly or indirectly) connected. In each of the chambers is a certain quantity of cheese. In chamber $$$i$$$ ($$$1 \leq i \leq n$$$) the cheese quantity is $$$c_i$$$. The network has an exit at chamber $$$n$$$.

A mouse is initially located in chamber $$$1$$$. At each step, the mouse will use its smell to detect the quantity of cheese in the neighbouring chambers, and will randomly choose to go through a tube with a likelihood proportional to the quantity of cheese in the corresponding chamber. The mouse will never consider going back to a previous chamber. If there's no next tube to choose, the mouse will get trapped.

Jerry wants to maximize the probability of the mouse to reach the exit. In order to do that, he may add cheese to any of the chambers. However, he can only add integral amounts of cheese to each chamber, and the total quantity must not exceed $$$x$$$.

How much cheese should Jerry add to each chamber, so that he maximizes the chances of the mouse escaping?

The first line of the input contains the numbers $$$n$$$ ($$$ 2 \leq n \leq 200\:000$$$) and $$$x$$$ ($$$1 \leq x \leq 10^9$$$).

The second line of the input contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_i \leq 10^9$$$).

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 \neq v_i)$$$, indicating that chambers $$$u_i$$$ and $$$v_i$$$ are directly connected by a tube.

It is guaranteed that the network of chambers is connected. Moreover, it is guaranteed that the total quantity of cheese initially in the chambers is at most $$$10^9$$$.

Output $$$n$$$ non-negative integers. The $$$i$$$-th integer represents the quantity of cheese that Jerry should add to the $$$i$$$-th chamber. If there are multiple solutions, you may output any of them.

5 5
1 2 3 2 1
1 2
1 3
2 4
2 5

0 2 0 0 3 

3 3
1 2 3
1 2
2 3

0 0 1