28321번 - Travelling Trader 스페셜 저지다국어

A trader would like to make a business of travelling between cities, moving goods from one city to another in exchange for a profit. There are $N$ cities labelled $1, \ldots, N$ and $N - 1$ roads. Each road joins two cities and takes one day to traverse. It is possible to reach any city from any other city using these roads.

The $i$-th city can give a profit of $p_i$ if the trader is currently in that city and chooses to do business in that city, but this profit may only be obtained once. The trader starts by doing business in city $1$ and wants to travel along the roads, visiting cities to maximize their total profit. However, the trader's boss will get unhappy and lay off the trader as soon as the trader goes more than $K$ days in a row without increasing their total profit. Note that the trader will take only one day to move between adjacent cities, regardless of whether the trader does business in either city. We would like to know the maximum profit the trader can make under this condition and a route that obtains this profit.

The first line of input contains two space-separated integers $N$ and $K$.

The next $N - 1$ lines of input each contain two space-separated integers $u_i$ and $v_i$ $(1 \le u_i,\,v_i \le N,\,u_i \neq v_i)$, describing a road.

The last line of input contains $N$ integers $p_1, \ldots, p_N$ $(1 \le p_i \le 10^9)$, the profits given by choosing to do business in the corresponding city.

On the first line, output the maximum possible total profit.

On the second line, output $M$ $(1 \le M \le N)$, the number of cities the trader does business in on an optimal route.

On the third line, output M space-separated integers $x_1, \ldots, x_M$, the cities the trader does business in on an optimal route in order, starting with $x_1 = 1$.

If there are multiple possible correct outputs, any correct output will be accepted.

• $2 \le N \le 200\,000$
• $1 \le K \le 3$