H. Ближе
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На вашем бизнес мероприятии есть $$$n$$$ потенциальных сделок.

Для каждой сделки нужны ровно два человека, и каждый человек ждёт ровно одну сделку. Другими словами, всего есть $$$2n$$$ человек, и каждый номер сделки $$$1 \ldots n$$$ встречается ровно у двух людей на бейджах.

По корпоративным причинам организаторы размещают каждого человека в уникальной вершине дерева с $$$2n$$$ вершинами. Вершина $$$v$$$ содержит человека с бейджем $$$a_v$$$.

Сделка $$$i$$$ считается заключённой, если в момент начала мероприятия два человека с бейджем $$$i$$$ находятся в соседних вершинах. Каждая заключённая сделка приносит вам прибыль $$$w_i$$$.

Перед началом мероприятия вам разрешено одно переставление:

  1. Выберите любое (возможно, пустое) множество рёбер такое, что никакие два выбранных ребра не имеют общей вершины (то есть выбранные рёбра образуют паросочетание).
  2. Для каждого выбранного ребра $$$(u, v)$$$ поменяйте местами людей в вершинах $$$u$$$ и $$$v$$$.

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

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

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

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

В следующей строке даны $$$n$$$ целых чисел $$$w_1, w_2, \ldots, w_n$$$ ($$$0 \leq w_i \leq 10^5$$$), где $$$w_i$$$ обозначает прибыль от сделки $$$i$$$.

В следующей строке даны $$$2n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2n}$$$. Гарантируется, что каждое значение $$$1, 2, \ldots, n$$$ встречается в массиве $$$a$$$ ровно два раза.

Следующие $$$2n-1$$$ строк содержат по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u, v, \leq 2n, u \neq v$$$) — ребро, соединяющее вершины $$$u$$$ и $$$v$$$.

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

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

Для каждого набора входных данных выведите одно целое число — максимальный суммарный доход после перестановки.

Пример
Входные данные
3
2
10 3
1 2 2 1
1 2
2 3
3 4
3
8 7 1
3 1 2 3 1 2
1 2
1 3
1 4
1 5
1 6
3
4 9 7
1 2 3 1 2 3
1 2
2 3
3 4
4 5
5 6
Выходные данные
10
8
11
Примечание

Набор входных данных 1. Поменяйте местами вершины на рёбрах $$$(1,2)$$$ и $$$(3,4)$$$ (они не имеют общих вершин). Тогда две единицы станут соседними на ребре $$$(2,3)$$$, принося $$$w_1=10$$$, что лучше, чем оставить существующее соседство 2—2, дающее 3.

Набор входных данных 2. Дерево — звезда. Обмен по ребру $$$(1,2)$$$ переносит бейдж 1 в центр, делая его соседним с другой 1, что приносит $$$w_1=8$$$.

Набор входных данных 3. Поменяйте местами вершины на рёбрах $$$(1,2), (3,4), (5,6)$$$, чтобы одновременно заключить две сделки: ребро $$$(2,3)$$$ становится 1—1 (прибыль 4), а ребро $$$(4,5)$$$ становится 3—3 (прибыль 7), всего 11.