P12449 [COTS 2025] 吸尘 / Usisavač

Mirko 有一所大房子，由 $N$ 个房间通过 $N-1$ 条走廊连接而成。每条走廊连接两个不同的房间，且所有房间互相连通。每条走廊长 $1$ 米。Mirko 经常打扫房间，但很少清理走廊。现在走廊积满灰尘，Mirko 想要用吸尘器清理它们。 每个吸尘器都有电缆长度限制。**每个房间有插座，吸尘器必须插入某个房间的插座才能工作**。Mirko 从房间 $1$ 出发，可以进行以下操作： - 若吸尘器未通电，他可以： - 将吸尘器插入当前所在房间的插座。 - 手持吸尘器移动到相邻房间。穿过走廊需 $1$ 分钟。 - 若吸尘器已通电，他可以： - 若处于插入吸尘器的房间，可以拔下插头。 - 移动到相邻房间并清理路径上的走廊。仅当电缆长度足够时可行（即插入插座房间与目标房间的距离不超过电缆长度）。清理走廊需 $1$ 分钟。 Mirko 的吸尘器坏了。现在商店有 $Q$ 台吸尘器，第 $i$ 台的电缆长度为 $r_i$ 米。他想知道对于每台吸尘器，清理所有走廊的最短时间。请帮他计算这些时间！

无

无

### 样例解释 样例 $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 为样例。 | 子任务编号 | $N\le$ | $Q\le$ | 特殊性质 | 得分 | | :-: | :-: | :-: | :-: | :-: | | $1$ | $10^3$ | $10^3$ | $-$ | $16$ | | $2$ | $3\times 10^5$ | $3\times 10^5$ | $\text{A}$ | $10$ | | $3$ | $3\times 10^5$ | $1$ | $-$ | $22$ | | $4$ | $10^5$ | $10^5$ | $-$ | $31$ | | $5$ | $3\times10^5$ | $3\times10^5$ | $-$ | $21$ | 特殊性质 $\text{A}$：$\forall 1\le i\le N-1$，存在一条连接 $i$ 和 $i+1$ 的走廊。