Problem Description

A trader wants to do business between cities, transporting goods from one city to another to make a profit. There are $N$ cities, numbered $1, \ldots, N$. There are $N-1$ roads, each connecting two cities, and each road takes one day to travel. Using these roads, it is possible to reach any city from any other city.

If the trader is currently in city $i$ and chooses to do business, they can earn a profit of $p_{i}$, but for each city, this profit can be earned at most once. The trader starts in city $1$, travels along the roads to visit cities, and wants to maximize their total profit. However, if the trader goes too long without earning profit, their boss will become unhappy. Specifically, once the trader goes for more than $K$ consecutive days without earning any profit, the boss will fire them. Note: regardless of whether the trader does business in a city, moving between adjacent cities still takes one day. You need to find the maximum profit the trader can obtain and a route that achieves it.

Find the maximum possible total profit the trader can earn, and construct one valid plan.

Input Format

The first line contains two integers $N$ and $K$, separated by spaces.

The next $N-1$ lines each contain two integers $u_{i}$ and $v_{i}$, separated by spaces, describing a road.

The last line contains $N$ integers $p_{1}, \ldots, p_{N}$, meaning the profit gained by choosing to do business in the corresponding city.

Output Format

The first line outputs one integer, the maximum possible total profit.

The second line outputs one integer $M\ (1 \leq M \leq N)$, the number of cities where the trader does business on an optimal route.

The third line outputs $M$ integers $x_{1}, \ldots, x_{M}$ separated by spaces, meaning the cities where the trader does business in order on the optimal route, starting with $x_1=1$.

If there are multiple correct solutions, you may output any of them.

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

7
2
1 3

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

14
5
1 4 5 2 3

Hint

Sample Explanation 1

On day $1$, the trader starts in city $1$ and does business there, earning a profit of $3$.

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

On day $3$, the trader cannot reach another city where they have not done business before being fired, so their total profit is $7$.

Sample Explanation 2

The trader visits in the order $1,2,4,2,5,2,1,3$, and can earn profit in every city.

Note that, to ensure they do not go more than $2$ days without earning profit, the trader delays doing business in city $2$.

Constraints: for all testdata, $2 \leq N \leq 2\times 10^5$, $1 \leq K \leq 3$, $1 \leq u_{i}, v_{i} \leq N$, $u_{i} \neq v_{i}$, $1 \leq p_{i} \leq 10^{9}$.

Translated by ChatGPT 5