F. Spectral Components
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево, состоящее из $$$n$$$ вершин. Каждая вершина $$$i$$$ окрашена в цвет $$$c_i$$$.

Для каждого цвета $$$c$$$, присутствующего на дереве, пусть $$$m_c$$$ — общее количество вершин цвета $$$c$$$. Вам также дан массив $$$k$$$ длиной $$$n$$$, где $$$k_c$$$ ($$$1 \le k_c \le m_c$$$) представляет собой целевой размер компоненты для цвета $$$c$$$.

Для каждого цвета $$$c$$$ независимо ваша задача состоит в том, чтобы выбрать связный подграф (компоненту), состоящий ровно из $$$k_c$$$ вершин. Вершины, выбранные вами для компоненты, не обязательно должны быть цвета $$$c$$$.

Стоимость выбранной компоненты — это сумма кратчайших расстояний от каждой вершины цвета $$$c$$$ до выбранной компоненты. (Расстояние от вершины $$$v$$$ до компоненты $$$S$$$ определяется как минимальное количество ребер на простом пути от $$$v$$$ до любой вершины $$$u$$$ в $$$S$$$).

Для каждого цвета $$$c$$$ от $$$1$$$ до $$$n$$$ найдите минимально возможную стоимость допустимой компоненты размера $$$k_c$$$. Если в дереве нет вершин цвета $$$c$$$, выведите $$$-1$$$ для этого цвета.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных указано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.

Во второй строке указаны $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le n$$$) — цвета вершин.

В третьей строке содержатся $$$n$$$ целых чисел $$$k_1, k_2, \ldots, k_n$$$ ($$$1 \le k_i \le n$$$) — целевые размеры компонент для каждого цвета. Гарантируется, что если цвет $$$c$$$ встречается в дереве $$$m_c \gt 0$$$ раз, то $$$1 \le k_c \le m_c$$$.

Каждая из следующих $$$n - 1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$), представляющих ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что заданные ребра образуют корректное дерево.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел. $$$c$$$-е число должно равняться минимально возможной стоимости допустимой составляющей размера $$$k_c$$$ для цвета $$$c$$$ или $$$-1$$$, если цвет $$$c$$$ отсутствует в дереве.

Пример
Входные данные
3
5
1 1 2 1 2
2 1 1 1 1
1 2
2 3
2 4
4 5
6
2 1 1 1 1 1
3 1 1 1 1 1
1 2
1 3
1 4
1 5
1 6
6
1 2 1 2 1 2
2 3 1 1 1 1
1 2
2 3
3 4
4 5
5 6
Выходные данные
1 3 -1 -1 -1
3 0 -1 -1 -1 -1
3 2 -1 -1 -1 -1
Примечание

В первом наборе входных данных дерево имеет $$$5$$$ вершин. Цвет $$$1$$$ встречается $$$3$$$ раза (вершины $$$1, 2, 4$$$). Цвет $$$2$$$ встречается $$$2$$$ раза (вершины $$$3, 5$$$). Цвета $$$3$$$, $$$4$$$ и $$$5$$$ не встречаются, поэтому для них выводится $$$-1$$$. Для цвета $$$1$$$ ($$$k_1 = 2$$$) мы можем выбрать компоненту $$$S = \{2, 4\}$$$. Расстояние от вершины $$$1$$$ до $$$S$$$ равно $$$1$$$. Расстояния от вершин $$$2$$$ и $$$4$$$ до $$$S$$$ равны $$$0$$$. Общая стоимость составляет $$$1 + 0 + 0 = 1$$$. Для цвета $$$2$$$ ($$$k_2 = 1$$$) оптимальной компонентой является единственная вершина $$$S = \{2\}$$$. Расстояние от $$$3$$$ до $$$2$$$ равно $$$1$$$, а от $$$5$$$ до $$$2$$$ — $$$2$$$. Общая стоимость равна $$$3$$$.

Во втором наборе входных данных дерево представляет собой звездообразный граф с центром $$$1$$$ (цвет $$$2$$$) и $$$5$$$ листьями (цвет $$$1$$$). Для цвета $$$1$$$ ($$$k_1 = 3$$$) оптимальной стратегией является включение центра и двух листьев, например, $$$S = \{1, 2, 3\}$$$. Расстояния от листьев цвета $$$1$$$ до $$$S$$$ равны $$$0$$$ (для $$$2, 3$$$) и $$$1$$$ (для $$$4, 5, 6$$$), что даёт минимальную стоимость $$$3$$$. Для цвета $$$2$$$ ($$$k_2 = 1$$$) единственной вершиной является сам центр. Выбор $$$S = \{1\}$$$ даёт стоимость $$$0$$$.

В третьем наборе входных данных дерево представляет собой линейный граф $$$1-2-3-4-5-6$$$ с чередующимися цветами. Для цвета $$$2$$$ (вершины $$$2, 4, 6$$$) нам нужна компонента размера $$$3$$$. Оптимальная компонента — $$$S = \{3, 4, 5\}$$$. Расстояния от вершин цвета $$$2$$$ до $$$S$$$ равны $$$1$$$ (от $$$2$$$ по ребру $$$2-3$$$), $$$0$$$ (от $$$4$$$, так как она входит в $$$S$$$) и $$$1$$$ (от $$$6$$$ по ребру $$$6-5$$$). Общая стоимость равна $$$2$$$.