Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The country **FurfuriNagar** is famous for the cartoon series **Motu Patlu**. The peace and furfuriness of the country were unbearable for the world's most terrifying gang **Jingalala**. Therefore they have decided to take control over the country.

There are $n$ cities numbered from $1$ to $n$ in FurfuriNagar. Each pair of cities are connected with exactly one simple path. More formally the cities maintain a tree structure. The gang Jingalala consists of $x$ terrorists. They want to start attacking from any arbitrary city of FurfuriNagar and take control over as many cities as possible. The $i$-th city has $a_i$ armies to protect the city. When the gang attacks a city, if the number of armies of that city is greater than the number of terrorists who attacked the city, then all the terrorists are killed and they can’t win that city. Otherwise, they kill half of the armies and the remaining armies join their gang. (Formally, they kill $\lceil\frac{a_i}{2} \rceil$ armies of the $i$-th city). Thus they win a city. After winning each city, the gang members of that city get divided into groups and attack the adjacent unattacked cities. The gang is not allowed to visit a city twice.

They know the map of FurfuriNagar and the number of armies of each city. Now it’s time to find the optimal way to divide the gang members after winning each city so that they can win as many cities as possible. Now for each city, they want to know the maximum number of cities they can win, if they start attacking from that city. As you are a good programmer, they kidnapped you to solve the task.

The first line of the input contains two integers $n$$(1 \leq n \leq 100)$ and $(1 \leq x \leq 10^{9}),$ denoting the number of cities and the number of terrorists.

The next line contains $n$ space-separated integers $a_1, a_2, \dots, a_n (1 \leq a_i \leq 10^{9})$ denoting the number of armies of each city.

Each of the following $n-1$ lines contains two integers $u$ and $v$ $(1 \leq u, v \leq n, u \neq v)$ denoting a road between the city $u$ and $v$.

Print $n$ space-separated integers. The $i$-th integer should be the maximum number of cities they can win if they start attacking from the $i$-th city.

Input | Output |
---|---|

7 3 3 2 4 4 5 1 2 1 2 2 3 2 4 1 5 5 6 5 7 | 3 5 0 0 0 1 1 |

Input | Output |
---|---|

5 3 4 1 2 5 3 1 2 1 3 1 4 1 5 | 0 1 4 0 4 |

100% Solution Ratio

YouKnowWhoEarliest,

Deshi_TouristFastest, 0.0s

YouKnowWhoLightest, 262 kB

Deshi_TouristShortest, 1277B

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.