| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 8 | 3 | 3 | 37.500% |
Рик и Морти обнаружили в другом измерении карту планеты, на которой изображены $n$ пунктов раскопок, соединенных тропинками. Тропинка с номером $i$ соединяет пункты с номерами $u_i$ и $v_i$ и имеет длину 1ドル$.
Разумеется, Рик сразу заметил, что количество тропинок равняется в точности $n - 1,ドル и из любого пункта можно добраться до любого другого. Иными словами, структура дорог и пунктов представляет из себя дерево, но для Морти это определение слишком сложное, поэтому Рик оставил Морти изучать теорию графов, а сам отправился исследовать это измерение.
Инопланетный информатор сообщил ему, что всего существует $k \leqslant 2$ видов артефактов, и в пункте номер $i$ хранится артефакт вида $a_i$. Так очень удачно совпало, что у Рика очередное соревнование с одним из известных расхитителей космических гробниц, и для победы Рику нужно собрать по одному экземпляру каждого из видов артефактов.
Одной из проблем является то, что внутри этого измерения не работают никакие продвинутые технологии. Поэтому Рик может заранее создать порталы в запланированных стартовом и конечном пункте маршрута, а вот остальной маршрут придется пройти пешком. Чтобы сэкономить свое время, Рик хочет заранее выбрать стартовый пункт, конечный пункт и сам путь (не обязательно простой) так, чтобы пройденное им расстояние было минимальным, и при этом на пути он бы собрал все различные виды артефактов.
Рик, конечно, и сам может справиться с поиском такого кратчашего пути, но, может быть, у вас есть время заняться этим, пока он собирает всю необходимую для путешествия экипировку?
В первой строке через пробел даны два целых числа $n$ и $k$ (2ドル \leqslant n \leqslant 10^5$; 1ドル \leqslant k \leqslant 2$) --- количество пунктов и необходимое количество артефактов.
В следующей строке через пробел даны $n$ целых чисел $a_i$ --- виды артефактов в каждом пункте (0ドル \leqslant a_i \leqslant k$). В случае, если $a_i = 0,ドル считается, что в вершине не хранится никакой из видов артефактов.
В следующих $n - 1$ строках даны пары целых чисел $u_i$ и $v_i,ドル обозначающие наличие тропинки между пунктами $u_i$ и $v_i$ (1ドル \leqslant u_i, v_i \leqslant n$). Гарантируется, что структура графа представляет из себя дерево.
В случае, если невозможно собрать $k$ различных видов артефактов выведите $-1,ドル иначе сообщите минимальное расстояние, которое придется пройти, чтобы собрать все виды артефактов.
5 2 1 1 2 2 2 1 3 2 3 3 4 4 5
1
5 1 1 0 1 0 1 1 3 2 3 3 4 4 5
0
4 2 0 1 2 1 1 2 2 4 1 3
2
В первом примере можно стартовый портал поставить в вершину 1ドル,ドル конечный в вершине 3ドル$. Для сбора всех видов артефактов нужно будет пройти ровно по одному ребру.
Во втором примере можно стартовый портал поставить в любую вершину с первым артефактом. И так как всего существует один тип, то его сразу соберут.
В третьем примере можно стартовый портал поставить в вершину 2ドル,ドル конечный в вершине 3ドル$. Для сбора всех видов артефактов нужно будет пройти ровно 2 ребра.