Это простая версия задачи. Разница между версиями заключается в том, что в этой версии $$$q \le 10$$$. Вы можете совершать взломы только если решили все версии этой задачи.

Вам дано дерево с $$$n$$$ вершинами, где каждая вершина пронумерована от $$$1$$$ до $$$n$$$. Каждому ребру также присвоен целый положительный вес $$$w_1, w_2, \ldots, w_{n-1}$$$.

Победоносная раскраска — это раскраска каждой вершины в два цвета: красный и желтый, при этом должна быть как минимум одна вершина, раскрашенная в красный (соответствующая символу команды T1).

Предположим, что каждой вершине присвоен целый неотрицательный вес $$$x_1, x_2, \ldots, x_n$$$. Стоимость победоносной раскраски определяется как сумма весов всех красных вершин, плюс сумма весов всех рёбер, которые соединяют вершины разных цветов (между красными и желтыми). Мы определяем $$$f([x_1, x_2, \ldots, x_n])$$$ как минимально возможную стоимость для всех победоносных раскрасок.

Гумаюси рассматривал задачу вычисления $$$f([x_1, x_2, \ldots, x_n])$$$ для заданной последовательности $$$x_1, x_2, \ldots, x_n$$$. Однако эта задача оказалась для него слишком простой, поэтому он придумал вариацию: по заданному целому числу $$$l$$$, найдите последовательность целых неотрицательных весов вершин $$$[x_1, x_2, \ldots, x_n]$$$, такую что $$$f([x_1, x_2, \ldots, x_n]) \ge l$$$ и общая сумма $$$\sum_{i=1}^n x_i$$$ минимальна.

Гумаюси был удовлетворен, но возникла серьезная проблема — у этой задачи нет никаких запросов, что является необходимым компонентом для любой задачи, которая не является плохой. Поэтому он добавил запросы к этой задаче. В запросе даётся значение $$$l$$$, и вы должны найти соответствующую минимально возможную сумму весов вершин.