Простая и сложная версии на самом деле являются разными задачами, поэтому прочитайте условия обеих задач внимательно.
Вам задано взвешенное корневое дерево, вершина \(1\) — корень этого дерева. Также каждое ребро имеет свою собственную стоимость.
Дерево — это связный граф без циклов. У корневого дерева есть специальная вершина, называемая корнем. Предком вершины \(v\) называется последняя отличная от \(v\) вершина на пути от корня к вершине \(v\). Потомками вершины \(v\) называются все вершины, для которых \(v\) является предком. Вершина называется листом, если у нее нет потомков. Взвешенное дерево — это такое дерево, в котором у каждого ребра есть некоторый вес.
Вес пути — это сумма весов всех ребер на этом пути. Вес пути от вершины до самой себя равен \(0\).
Вы можете совершить последовательность из нуля или более ходов. В течение одного хода вы можете выбрать ребро и поделить его вес на \(2\) с округлением вниз. Более формально, в течение одного хода вы выбираете какое-то ребро \(i\) и делите его вес на \(2\) с округлением вниз (\(w_i := \left\lfloor\frac{w_i}{2}\right\rfloor\)).
Каждое ребро \(i\) имеет свою стоимость \(c_i\), которая равна либо \(1\), либо \(2\) монетам. Каждый ход с ребром \(i\) стоит \(c_i\) монет.
Ваша задача — найти минимальную суммарную стоимость, необходимую для того, чтобы сделать сумму весов путей от корня до каждого листа не превосходящей \(S\). Другими словами, если \(w(i, j)\) — это вес пути от вершины \(i\) до вершины \(j\), то вам необходимо сделать \(\sum\limits_{v \in leaves} w(root, v) \le S\), где \(leaves\) — это список всех листьев.
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите ответ на него: минимальную суммарную стоимость, необходимую, чтобы сделать сумму весов путей от корня до каждого листа не превосходящей \(S\).