410170: GYM103967 F Артефакты
Description
Рик и Морти обнаружили в другом измерении карту планеты, на которой изображены $$$n$$$ пунктов раскопок, соединенных тропинками. Тропинка с номером $$$i$$$ соединяет пункты с номерами $$$u_i$$$ и $$$v_i$$$ и имеет длину $$$c_i$$$.
Разумеется, Рик сразу заметил, что количество тропинок равняется в точности $$$n - 1$$$, и из любого пункта можно добраться до любого другого. Иными словами, структура дорог и пунктов представляет из себя дерево, но для Морти это определение слишком сложное, поэтому Рик оставил Морти изучать теорию графов, а сам отправился исследовать это измерение.
Инопланетный информатор сообщил ему, что всего существует $$$k$$$ видов артефактов, и в пункте номер $$$i$$$ хранится артефакт вида $$$a_i$$$. Так очень удачно совпало, что у Рика очередное соревнование с одним из известных расхитителей космических гробниц, и для победы Рику нужно собрать все $$$k$$$ различных видов артефактов.
Одной из проблем является то, что внутри этого измерения не работают никакие продвинутые технологии. Поэтому Рик может заранее создать порталы в запланированных стартовом и конечном пункте маршрута, а вот остальной маршрут придется пройти пешком. Чтобы сэкономить свое время, Рик хочет заранее выбрать стартовый пункт, конечный пункт и сам путь (не обязательно простой) так, чтобы пройденное им расстояние было минимальным, и при этом на пути он бы собрал все различные виды артефактов.
Рик, конечно, и сам может справиться с поиском такого кратчашего пути, но, может быть, у вас есть время заняться этим, пока он собирает всю необходимую для путешествия экипировку?
Входные данныеВ первой строке через пробел даны два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leqslant n \leqslant 10^5$$$; $$$1 \leqslant k \leqslant 6$$$) — количество пунктов и необходимое количество артефактов.
В следующей строке через пробел даны $$$n$$$ целых чисел $$$a_i$$$ — виды артефактов в каждом пункте ($$$0 \leqslant a_i \leqslant k$$$). В случае, если $$$a_i = 0$$$, считается, что в вершине не хранится никакой из видов артефактов.
В следующих $$$n - 1$$$ строках даны тройки целых чисел $$$u_i$$$, $$$v_i$$$, $$$c_i$$$, обозначающие наличие тропинки длины $$$c_i$$$ между пунктами $$$u_i$$$ и $$$v_i$$$ ($$$1 \leqslant u_i, v_i \leqslant n$$$; $$$1 \leqslant c_i \leqslant 10^9$$$). Гарантируется, что структура графа представляет из себя дерево.
Выходные данныеВ случае, если невозможно собрать $$$k$$$ различных видов артефактов, выведите «-1» (без кавычек), иначе сообщите минимальное расстояние, которое придется пройти, чтобы собрать все виды артефактов.
ПримерыВходные данные5 4 1 3 2 4 4 1 3 1 2 3 1 3 4 1 4 5 1Выходные данные
4Входные данные
5 5 1 3 2 4 4 1 3 1000 2 3 5123 3 4 3341 4 5 7197Выходные данные
-1Входные данные
4 3 0 1 2 3 1 2 10 2 3 1 3 4 50Выходные данные
51Примечание
В первом примере одним из оптимальных путей будет $$$1 \to 3 \to 2 \to 3 \to 4$$$.
В втором примере у нас нет пункта, в котором находится артефакт под номером $$$5$$$, а значит невозможно собрать все пять артефактов.
В третьем примере одним из оптимальных путей будет $$$2 \to 3 \to 4$$$.