Logo Infinity Online Judge

InfOJ

时间限制:3 s 空间限制:512 MB

#7. 路径

统计

题目描述

给定一棵树,求所有经过点数大于等于二的无向路径中长度第 $k$ 小的。多组询问。

输入格式

第一行两个整数 $n,q$,分别为点数和询问数。

接下来 $n-1$ 行,每行三个整数 $x,y,z$,表示 $x$ 到 $y$ 的边长度为 $z$。

接下来 $q$ 行,每行一个整数 $k$。保证存在至少 $k$ 条路径。

输出格式

$q$ 行,每行一个整数,为答案。

样例

输入

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

输出

3
3
4
6
7
7

说明

本题捆绑测试,时间限制 $3$ 秒。

对于 $100\%$ 的数据,$1\le n\le 5\times 10^4$,$1\le q\le 2\times 10^5$,$1\le x,y\le n$,$1\le \sum z\le 2\times 10^5$。详细数据范围如下。

Subtask 1(10 pts):$n,q\le 200$。

Subtask 2(10 pts):$n,q\le 10^3$。

Subtask 3(10 pts):$n\le 10^3$。

Subtask 4(10 pts):$q\le 10$。

Subtask 5(60 pts):没有任何附加限制。