| Codeforces Round 292 (Div. 1) |
|---|
| Закончено |
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.
5
1 2 3
2 3 4
4 5 3
3 4 2
5
1 2 3 4 5
1
3
3
3
5
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
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 мы можем выбрать все комнаты.
