— To count graph diameters.
You and Your Submission
Дерево — это неориентированный связный граф без циклов. Взвешенное дерево — это дерево, каждому ребру которого назначен некоторый вес. Степень вершины — это количество ребер, прилегающих к данной вершине.
Вам дано взвешенное дерево с \(n\) вершинами, каждое ребро которого имеет вес \(1\). Определим множество вершин \(L\) следующим образом: все вершины, степень которых равна \(1\), входят в это множество, остальные вершины в это множество не входят.
Вам необходимо ответить на \(q\) независимых запросов. В \(i\)-м запросе:
- Вам дано целое положительное число \(x_i\).
- Для всех \(u,v \in L\) таких, что \(u < v\), добавьте ребро \((u, v)\) с весом \(x_i\) в граф (который изначально является данным вам деревом).
- Найдите диаметр итогового графа.
Диаметр графа равен \(\max\limits_{1 \le u < v \le n}{\operatorname{d}(u, v)}\), где \(\operatorname{d}(u, v)\) — это длина кратчайшего пути между вершинами \(u\) и \(v\).
Выходные данные
В единственной строке выведите \(q\) целых чисел, которые являются ответами на запросы.
Примечание
Граф в первом тесте после добавления ребер:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 2
4
1 2 3 4
|
1 2 2 2
|
|
2
|
7
1 2 3 4 2 1
7
2 1 3 7 5 6 4
|
3 3 4 5 5 5 4
|
|
3
|
3
1 2
1
1
|
1
|