Олимпиадный тренинг

Задача . E. DZY любит садоводство

Задача

DZY любит садоводство, поэтому он обожает решать задачи про деревья.

У DZY есть взвешенное дерево (связный неориентированный граф без циклов), состоящее из n вершин (пронумерованных от 1 до n). Определим функцию g(x, y) (1 ≤ x, y ≤ n) как длину самого длинного ребра в кратчайшем пути между вершинами x и y. В частности, g(z, z) = 0 для любого z.

Для каждой целочисленной последовательности p₁, p₂, ..., p_n (1 ≤ p_i ≤ n), определим f(p) как $\text{[math]}$ .

DZY хочет найти такую последовательность p, что f(p) принимает максимальное возможное значение. Есть еще одно ограничение: элемент j может встречаться в p не более x_j раз.

Пожалуйста, помогите DZY, найдите максимальное возможное f(p) при описанных ограничениях.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 3000).

В каждой из следующих n - 1 строк записано по три целых числа a_i, b_i, c_i (1 ≤ a_i, b_i ≤ n; 1 ≤ c_i ≤ 10000), обозначающих ребро между вершинами a_i и b_i длины c_i. Гарантируется, что эти ребра образуют дерево.

Каждая из следующих n строк описывает элемент последовательности x. В j-й строке записано целое число x_j (1 ≤ x_j ≤ n).

Выходные данные

Выведите единственное целое число — ответ на задачу.

Примечание

В первом примере одна из оптимальных последовательностей p равна [4, 3, 2, 1].

Примеры

№	Входные данные	Выходные данные
1	4 1 2 1 2 3 2 3 4 3 1 1 1 1	2
2	4 1 2 1 2 3 2 3 4 3 4 4 4 4	3

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет