Две подруги, Алиса и Юки, посадили в своем саду дерево из \(n\) вершин. Дерево — это неориентированный граф без циклов, петель и кратных ребер. Каждое ребро в этом дереве имеет длину \(k\). Изначально вершина \(1\) — корень дерева.
Алиса и Юки выращивают дерево не просто так, они хотят продать его. Стоимостью дерева назовем максимальное расстояние от корня до вершины по всем вершинам дерева. Расстоянием между двумя вершинами \(u\) и \(v\) является сумма длин ребер на пути от \(u\) до \(v\).
Девочки проходили курс юных садоводов, поэтому они умеют модифицировать дерево. За \(c\) монет Алиса и Юки могут поменять корень дерева, выбрав одного из соседей текущего корня и сделав его корнем дерева. Эту операцию можно применять любое количество раз (в том числе и ноль). Обратите внимание, что операция не затрагивает структуру дерева; единственное изменение заключается в том, что корнем дерева становится другая вершина.
Подруги хотят продать дерево с максимальной выгодой. Выгода — это разность стоимости дерева и затрат на все операции.
Помогите девочкам и найдите максимальную выгоду, которую они могут получить, применив к дереву операции произвольное число раз (возможно, ноль).