题目描述

译自 $CCO$ $2023$ $Day2$ $T2$「$Travelling$ $Trader$」。

有 $N$ 个城市，编号为 $1, \ldots, N$，城市间有 $N-1$ 条道路。每条道路连接两个城市，穿越需 $1$ 天时间，且任意两个城市可通过道路互通（即城市构成一棵树）。

商人从城市 $1$ 出发，沿道路访问城市并做生意。在城市 $i$ 做生意可获得 $p_i$ 的利润，每个城市的利润仅能获得一次。商人需最大化总利润，但有约束：连续超过 $K$ 天未获得利润时，会被老板解雇。注意，城市间移动无论是否做生意，均消耗 $1$ 天时间。

你的任务是求出商人可获得的最大总利润，以及对应的最优路线（需输出做生意的城市顺序）。

输入格式

• 第一行：两个整数 $N$ 和 $K$（空格分隔）。
• 接下来 $N-1$ 行：每行两个整数 $u_i$ 和 $v_i$（空格分隔），表示一条连接城市 $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$ 为起点）。

若有多个最优方案，输出任意一个即可。

样例 1

输入

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

输出

7
2
1 3

说明

1. 第 $1$ 天：在城市 $1$ 做生意，获得利润 $3$。
2. 第 $2$ 天：移动到城市 $3$ 并做生意，获得利润 $4$（累计 $7$）。
3. 第 $3$ 天：无法在被解雇前到达未做生意的城市，行程结束。

样例 2

输入

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

输出

14
5
1 4 5 2 3

说明

商人的访问路线为 $1 \to 2 \to 4 \to 2 \to 5 \to 2 \to 1 \to 3$，在所有城市均做了生意。为避免连续超过 $2$ 天无利润，商人推迟了在城市 $2$ 做生意的时间。

数据范围与提示

• 所有数据：$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$。
• 子任务信息如下：