Вам дана бинарная строка $$$s$$$ длиной $$$n$$$ и дерево $$$T$$$ с $$$n$$$ вершинами. Пусть $$$k$$$ — это количество 1 в $$$s$$$. Мы построим полный неориентированный взвешенный граф с $$$k$$$ вершинами следующим образом:
Простой путь$$$^{\text{†}}$$$, который посещает вершины $$$v_1, v_2, \ldots, v_m$$$ в данном порядке, называется красивым, если для всех $$$1\le i\le m - 2$$$ выполняется условие $$$2\cdot w(v_i, v_{i + 1})\le w(v_{i + 1}, v_{i + 2})$$$. Другими словами, вес каждого ребра в пути должен быть как минимум в два раза больше веса предыдущего ребра. Обратите внимание, что $$$s_{v_i} = \mathtt{1}$$$ должно выполняться для всех $$$1\le i\le m$$$, иначе вершины с таким номером не будет.
Для каждой вершины с номером $$$i$$$ ($$$1\le i\le n$$$ и $$$s_i = \mathtt{1}$$$) в полном неориентированном взвешенном графе определите максимальное количество вершин на красивом простом пути, начинающемся с вершины $$$i$$$.
$$$^{\text{∗}}$$$Расстояние между двумя вершинами $$$a$$$ и $$$b$$$ в дереве равно количеству рёбер на уникальном простом пути между вершиной $$$a$$$ и вершиной $$$b$$$.
$$$^{\text{†}}$$$Путь — это последовательность вершин $$$v_1, v_2, \ldots, v_m$$$, такая что между $$$v_i$$$ и $$$v_{i + 1}$$$ есть ребро для всех $$$1\le i\le m - 1$$$. Простой путь — это путь без повторяющихся вершин, т.е. $$$v_i\neq v_j$$$ для всех $$$1\le i \lt j\le m$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 7\cdot10^4$$$) — длина бинарной строки $$$s$$$ и количество вершин в дереве $$$T$$$.
Вторая строка каждого набора входных данных содержит бинарную строку из $$$n$$$ символов $$$s_1s_2\ldots s_n$$$ ($$$s_i\in \{\mathtt{0}, \mathtt{1}\}$$$) — строку, представляющую вершины, которые будут построены в полном неориентированном взвешенном графе.
Каждая из следующих $$$n - 1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1\le u, v\le n$$$) — концы рёбер дерева $$$T$$$.
Гарантируется, что заданные рёбра образуют дерево.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$7\cdot10^4$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел. $$$i$$$-е целое число представляет максимальное количество вершин в красивом простом пути, начинающемся с вершины $$$i$$$. Если вершины с номером $$$i$$$ нет, т.е. $$$s_i = \mathtt{0}$$$, выведите $$$-1$$$.
35011111 22 33 44 517011010111101011011 22 33 44 55 66 77 88 99 1010 1111 1212 1313 1414 1515 1616 172011 2
-1 3 3 3 3 -1 5 4 -1 4 -1 5 5 5 5 -1 4 -1 5 5 -1 3 -1 1
В первом наборе входных данных дерево $$$T$$$ и построенный граф выглядят следующим образом:
Слева показано дерево $$$T$$$ с выделенными вершинами, окрашенными в желтый цвет. Справа — построенный полный граф. Красивый путь, показанный на картинке, это $$$3\rightarrow 4\rightarrow 2$$$. Путь красивый, так как $$$w(4, 2) = 2$$$ как минимум в два раза больше, чем $$$w(3, 4) = 1$$$. Расширить путь, используя $$$2\rightarrow 5$$$, невозможно, так как $$$w(2, 5) = 3$$$ меньше, чем удвоенный $$$w(4, 2) = 2$$$.
Во втором наборе входных данных дерево $$$T$$$ является простым путем длиной $$$17$$$. Пример красивого пути, начинающегося с вершины с числом $$$2$$$, это $$$2\rightarrow 3\rightarrow 5\rightarrow 9\rightarrow 17$$$, который имеет веса рёбер $$$1, 2, 4, 8$$$, удваивающиеся каждый раз.
| Codeforces Round 1024 (Div. 1) |
|---|
| Закончено |
