← 返回题目列表

Codeforces · 516/D

D. Drazil 和晨练

中文机器翻译题面 查看原题

Drazil 和 Varda 是蚯蚓夫妇。他们想找到一个好地方来抚养孩子。他们发现了一个含有自然洞的好地方。洞里有很多房间,有些房间之间有小隧道相连,蚯蚓可以在它们之间移动。

让我们将房间和小隧道视为图中的顶点和边。该图是一棵树。换句话说,任何一对顶点之间都有唯一的路径。

图中叶子的每个房间都通过垂直隧道与地面连接。这里,叶子是图中只有一个出边的顶点。

每个房间的大小只能容纳一只蚯蚓。蚯蚓不能生活在隧道里。

Drazil 和 Varda 有一个教育孩子的计划。他们希望所有的孩子起床后立即做早操!

早晨来临,所有的蚯蚓小朋友都在同一时间起床,然后每个人都选择到地面最远的路径与其他小朋友集合(这些小朋友很懒,所以他们都想尽可能晚地锻炼身体)。

Drazil和Varda希望第一个蚯蚓孩子到达外面的时间和最后一个蚯蚓孩子到达外面的时间之间的差值不大于l(否则孩子们会散布在地面上,很难让他们一起锻炼)。

此外,孩子们占用的房间应该形成一个相连的集合。换句话说,对于任意两个被蚯蚓孩子占据的房间,位于它们之间的路径上的所有房间也应该被蚯蚓孩子占据。

为了满足上述所有条件,Drazil 和 Varda 最多可以有多少个孩子? Drazil 和 Varda 想知道 l 的许多不同选择的答案。

(Drazil 和 Varda 并不和他们的孩子一起住在洞里)

输入

第一行包含一个整数 n 表示洞中有多少个房间 (2 ≤ n ≤ 105)。

接下来有 ​​n - 1 行。每行包含三个整数 x, y, v (1 ≤ x, y ≤ n, 1 ≤ v ≤ 106),表示房间 x 和房间 y 之间有一条小隧道,需要时间 v 通过。

假设一条蚯蚓从任意叶室爬出地面的时间是相同的。

下一行包含一个整数 q (1 ≤ q ≤ 50),表示需要处理的不同 l 值的个数。

最后一行包含 q 个数字,每个数字表示 l 值 (1 ≤ l ≤ 1011)。

输出

你应该打印 q 行。每一行应包含一个整数,表示相应 l 值的答案。

示例

输入 #1

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

输出 #1

1
3
3
3
5

输入 #2

12
5 9 3
2 1 7
11 7 2
6 5 5
2 5 3
6 7 2
1 4 4
8 5 7
1 3 8
11 12 3
10 8 2
10
13 14 14 13 13 4 6 7 2 1

输出 #2

10
10
10
10
10
3
3
5
2
1

注意

对于第一个示例,孔如下所示。 1 号和 5 号房间是树叶,因此它们包含一条连接到地面的垂直隧道。从1-5号房间到地面的最远路径长度分别为12、9、7、9、12。

如果l = 1,我们只能选择任何单间。

如果 l = 2..4,我们可以选择房间 2、3 和 4 作为答案。

如果l = 5,我们可以选择所有房间。