Merchants’ Profit Route

A merchant wants to make a profit by doing business in different cities. There are \(N\) cities numbered \(1,2,\ldots,N\) connected by \(N-1\) roads forming a tree. Each road connects two cities and takes one day to travel. In each city \(i\), if the merchant chooses to do business there, he gains a profit of \(p_i\); however, each city's profit can only be collected once.

The merchant starts at city \(1\) and travels along the roads. The objective is to choose a route and decide in which cities to do business so that the total profit is maximized. There is a catch: if the merchant goes more than \(K\) consecutive days without gaining any profit, his boss will fire him. In other words, if the merchant collects profit at a city, the "no-profit counter" resets. When traveling from one city where he did business to the next city where he does business, the number of days (i.e. the number of roads traversed on the unique simple path) must not exceed \(K\).

Formally, suppose the merchant chooses a sequence of distinct cities \(v_1, v_2, \ldots, v_m\) where he does business. It is required that \(v_1=1\) and for every consecutive pair \((v_i,v_{i+1})\), the distance (i.e. the number of roads on the unique simple path in the tree) satisfies \[ d(v_i,v_{i+1})\le K. \] Your task is to compute the maximum total profit the merchant can obtain and output one corresponding route (i.e. the sequence \(v_1,v_2,\ldots,v_m\)) that achieves this profit.

inputFormat

The first line contains two integers \(N\) and \(K\) (number of cities and the maximum allowed consecutive days without profit).

The second line contains \(N\) integers: \(p_1, p_2, \ldots, p_N\), where \(p_i\) denotes the profit available at city \(i\).

The following \(N-1\) lines each contain two integers \(u\) and \(v\), indicating that there is a road connecting cities \(u\) and \(v\).

outputFormat

Output two lines:

• The first line contains a single integer, the maximum total profit.
• The second line contains the sequence of cities (separated by a space) at which the merchant does business, in the order they are visited. If there are multiple solutions, output any one of them.

sample

4 2
5 10 15 20
1 2
2 3
2 4

50
1 2 3 4