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

Вам задано взвешенное корневое дерево, вершина $$$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$$$ независимых наборов тестовых данных.