题目描述

Mirko 有一所大房子，由 $N$ 个房间通过 $N-1$ 条走廊连接而成。每条走廊连接两个不同的房间，且所有房间互相连通。每条走廊长 $1$ 米。Mirko 经常打扫房间，但很少清理走廊。现在走廊积满灰尘，Mirko 想要用吸尘器清理它们。

每个吸尘器都有电缆长度限制。每个房间有插座，吸尘器必须插入某个房间的插座才能工作。Mirko 从房间 $1$ 出发，可以进行以下操作：

• 若吸尘器未通电，他可以：
  • 将吸尘器插入当前所在房间的插座。
  • 手持吸尘器移动到相邻房间。穿过走廊需 $1$ 分钟。
• 若吸尘器已通电，他可以：
  • 若处于插入吸尘器的房间，可以拔下插头。
  • 移动到相邻房间并清理路径上的走廊。仅当电缆长度足够时可行（即插入插座房间与目标房间的距离不超过电缆长度）。清理走廊需 $1$ 分钟。

Mirko 的吸尘器坏了。现在商店有 $Q$ 台吸尘器，第 $i$ 台的电缆长度为 $r_i$ 米。他想知道对于每台吸尘器，清理所有走廊的最短时间。请帮他计算这些时间！

输入格式

$N$ $Q$
$x_1$ $y_1$
$\vdots\quad\vdots$
$x_{N-1}$ $y_{N-1}$
$r_1$ $r_2$ $\cdots$ $r_Q$

其中，$\forall 1\le i\le N-1$，$(x_i,y_i)$ 描述一条连接 $x_i$ 和 $y_i$ 的走廊。

输出格式

输出一行 $Q$ 个数，其中第 $i$ 个数表示使用第 $i$ 台吸尘器时的最短清理时间。

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

8 4

10 2
1 2
2 4
5 2
6 3
3 1
6 7
9 7
8 6
8 10
1 3

24 16

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

6 12

提示

样例解释

样例 $1$ 解释：对于 $r_i=2$ 的询问，一个最优方案如下：

• 从房间 $1$ 走到房间 $3$。（$2$ 分钟）
• 在房间 $3$ 插入吸尘器。
• 吸尘房间 $3,4$ 间以及房间 $4,5$ 间的走廊（$2$ 分钟）。
• 返回房间 $3$。（$2$ 分钟）
• 吸尘房间 $3,2$ 间以及房间 $2,1$ 间的走廊（$2$ 分钟）。这样所有走廊都已清理干净。

数据范围

• $2 \leq N \leq 3 \times 10^5$；
• $1 \leq Q \leq 3 \times 10^5$；
• $1\le x_i,y_i\le N$；
• $x_i\neq y_i$；
• 任意两个房间都通过走廊连通；
• $1\le r_i\le N$；
• 所有输入的数均为整数。

子任务

Subtask 0 为样例。

特殊性质 $\text{A}$：$\forall 1\le i\le N-1$，存在一条连接 $i$ 和 $i+1$ 的走廊。