Мадока пересмотрела абсолютно все веселые видео-нарезки котиков, собачек и горилл на тутубе. Даже скупила абсолютно все колбасные, сырные, да и любые другие нарезки в местном магазине, так что теперь её продавщица не пускает в него. Мадоке захотелось продолжения.
Недавно она нашла на даче у своей бабушки растущее взвешенное дерево из $$$n$$$ вершин, у которого каждая вершина $$$i$$$ ($$$1 \le i \le n$$$) имеет вес $$$c_i$$$. Рядом с деревом лежала книга, где написано: «Напомним, что деревом называется граф без циклов, где между любыми двумя вершинами существует путь».
Мадока решила снять веселую нарезку взвешенного дерева и выложить её на набирающей популярность площадке «ТеремокТВ», где любое видео может легко набрать несколько десятков просмотров. Она хочет разбить бабушкино дерево на некоторое количество непересекающихся путей. Другими словами, каждая вершина должна принадлежать ровно одному простому пути.
Красотой простого пути $$$v_1, v_2, \ldots, v_k$$$ она считает значение $$$(c_{v_1} | c_{v_2} | \ldots | c_{v_k})^2$$$ (квадрат побитового ИЛИ весов вершин). Красотой разбиения будем считать сумму красот путей, на которые дерево распалось.
Помогите Мадоке стать популярной и набрать сотню просмотров. Найдите минимальную (у Мадоки очень странное понимание красоты) красоту дерева по всем его веселым нарезкам.
В первой строке задано единственное число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Затем следует их описание.
В первой строке каждого набора входных данных задано единственное число $$$n$$$ ($$$2 \leq n \leq 500$$$) — количество вершин в дереве.
Во второй строке каждого набора входных данных заданы числа $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_i \leq 10^7$$$) — веса вершин дерева.
В следующих $$$n - 1$$$ строках идёт описание рёбер графа.
Каждое ребро задано в отдельной строке числами $$$u, v$$$ ($$$1 \leq u, v \leq n$$$) — означающее ребро между вершинами $$$u, v$$$.
Гарантируется, что каждый тест задает корректное дерево, и что сумма $$$n$$$ по всем наборам входных не превосходит $$$500$$$.
Для каждого набора входных данных выведите ровно одно число — ответ на задачу.
267 5 4 1 21 101 21 32 45 36 5571 56 63 59 973 43 25 44 1
590 18419
В первом наборе входных данных оптимальное разбиение выглядит так:
Красота такого разбиения: $$$10^2 + (21|4)^2 + (7|5|1)^2 = 590$$$. Можно показать, что красоту меньше получить нельзя.
