描述
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, . . . , 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 pi
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.
输入描述
```c++
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 ui and vi (1 ≤
ui
, vi ≤ N, ui ̸= vi), describing a road.
The last line of input contains N integers p1, . . . , pN (1 ≤ pi ≤ 109
), 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 ≤ M ≤ N), the number of cities the trader does business
in on an optimal route.
On the third line, output M space-separated integers x1, . . . , xM, the cities the trader does
business in on an optimal route in order, starting with x1 = 1.
If there are multiple possible correct outputs, any correct output will be accepted.
样例输入 1
4 1
1 2
1 3
2 4
3 1 4 1
样例输出 1
7
2
1 3
样例输入 2
5 2
1 2
1 3
2 4
2 5
3 1 4 1 5
样例输出 2
14
5
1 4 5 2 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.
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.
