Canadian Computing Olympiad: 2023 Day 2, Problem 2

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.

Input Specification

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.

Marks Awarded	Bounds on ~N~	Bounds on ~K~
~2~ marks	~2 \le N \le 200\,000~	~K=1~
~7~ marks	~2 \le N \le 200~	~K=2~
~3~ marks	~2 \le N \le 2\,000~	~K=2~
~4~ marks	~2 \le N \le 200\,000~	~K=2~
~4~ marks	~2 \le N \le 2\,000~	~K=3~
~5~ marks	~2 \le N \le 200\,000~	~K=3~

Output Specification

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.

Sample Input 1

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

Output for Sample Input 1

7
2
1 3

Explanation of Output for Sample Input 1

On day ~1~, the trader starts by doing business in city ~1~, making a profit of ~3~.

On day ~2~, the trader moves to city ~3~ and does business there, making a profit of ~4~.

At this point, the trader cannot reach another city in which they have not done business before getting laid off, so their total profit is ~7~.

Sample Input 2

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

Output for Sample Input 2

14
5
1 4 5 2 3

Explanation of Output for Sample Input 2

The trader can make a profit in every city by visiting them in the order ~1, 2, 4, 2, 5, 2, 1, 3~.

Note that the trader strategically delays doing business in city ~2~ to ensure they do not go more than ~2~ days without making a profit.