题目描述

一个商人想要在城市之间做生意，把货物从一个城市运到另一个城市来获得利润。有 $N$ 个城市，用 $1, \ldots, N$ 表示。有 $N-1$ 条道路，每条道路连接两个城市，每条道路需要一天的时间来穿越。使用这些道路，可以从任何一个城市到达另一个城市。

如果商人当前在第 $i$ 个城市并选择做生意，那么商人可以获得 $p_{i}$ 的利润，但是对于每个城市这个利润只能获得一次。商人从第 $1$ 个城市开始做生意，沿着道路访问城市，以最大化他们的总利润。但是如果商人太久没有获得利润，商人的老板会变得不高兴。具体地说，一旦商人连续超过 K 天没有获得利润，老板就会解雇商人。注意：无论商人是否在其中一个城市做生意，商人在相邻的城市之间移动都需要一天的时间。你需要求出商人可以获得的最大利润和能够获得这个利润的路线。

求出商人能得到的可能的最大总利润，并构造一种方案。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $K$。

接下来的 $N-1$ 行，每行包含两个用空格分隔的整数 $u_{i}$ 和 $v_{i}$，表示一条道路。

最后一行包含 $N$ 个整数 $p_{1}, \ldots, p_{N}$，表示选择在相应的城市做生意所给的利润。

输出格式

第一行输出一个整数，表示可能的最大总利润。

第二行输出一个整数 $M\ (1 \leq M \leq N)$，表示在最优路线上商人做生意的城市的数量。

第三行，输出 $M$ 个用空格分隔的整数 $x_{1}, \ldots, x_{M}$，表示商人按顺序在最优路线上做生意的城市，从 $x_1=1$ 开始。

如果有多个正确方案，你可以输出任何一个。

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

提示

样例解释 1

在第 $1$ 天，商人从第 $1$ 个城市开始做生意，获得 $3$ 的利润。

在第 $2$ 天，商人移动到第 $3$ 个城市，并在那里做生意，获得 $4$ 的利润。

在第 $3$ 天，商人无法在被解雇之前到达另一个他们没有做过生意的城市，所以他们的总利润是 $7$。

样例解释 2

商人按照 $1,2,4,2,5,2,1,3$ 的顺序访问它们，可以在每个城市获得利润。

注意，商人为了确保他们不会超过 $2$ 天没有获得利润，推迟了在第 $2$ 个城市做生意的时间。

对于所有数据，有 $2 \leq N \leq 2\times 10^5，1\leq K\le 3，1 \leq u_{i}, v_{i} \leq N，u_{i} \neq v_{i}，1 \leq p_{i} \leq 10^{9}$。