Practice on Toph

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

Battle of FurfuriNagar

By adnan_toky · Limits 2s, 512 MB

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 nn cities numbered from 11 to nn 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 xx terrorists. They want to start attacking from any arbitrary city of FurfuriNagar and take control over as many cities as possible. The ii-th city has aia_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 ai2\lceil\frac{a_i}{2} \rceil armies of the ii-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 nn(1n100)(1 \leq n \leq 100) and (1x109),(1 \leq x \leq 10^{9}), denoting the number of cities and the number of terrorists.

The next line contains nn space-separated integers a1,a2,,an(1ai109)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 n1n-1 lines contains two integers uu and vv (1u,vn,uv)(1 \leq u, v \leq n, u \neq v) denoting a road between the city uu and vv.


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


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 
5 3
4 1 2 5 3
1 2
1 3
1 4
1 5
0 1 4 0 4 



100% Solution Ratio

YouKnowWhoEarliest, 8M ago

Deshi_TouristFastest, 0.0s

YouKnowWhoLightest, 262 kB

Deshi_TouristShortest, 1277B


Login to submit

Related Contests

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