Авторы задачи и разработчики: Владимир Новиков, Максим Дмитриев
У авторов есть два разных решения, в разборе будет приведено одно из них, альтернативное можно посмотреть в разборе продвинутой версии.
Сразу обозначим за $$$mask$$$ описание набора артефактов, которые мы успели собрать. Это будет число от $$$0$$$ до $$$3$$$, где $$$0$$$ — нет собранных артифактов, $$$1$$$ и $$$2$$$ — собран первый или второй артифакт, $$$3$$$ — собраны оба.
Утверждение: оптимальный обход — это сумма ребер, взятых дважды, минус сумма ребер на диаметре нашего пути. Это следует просто из рассмотрения выбранного маршрута: его можно представить как непрерывный простой путь, от которого ответвляются поддеревья, на которых каждое ребро обходится в обе стороны (чтобы обойти все дерево и вернуться на «основной» маршрут).
Будем решать задачу с помощью поиска в ширину. Для каждой вершины создадим $$$2^k$$$ ее копий, отвечающих разным наборам артефактов. Пусть $$$\mathtt{dp}[i][mask]$$$ — минимальный ответ на задачу, если мы закончили наш путь в вершине $$$i$$$, предварительно посетив $$$mask$$$ артефактов. Тогда мы можем запустить поиск в ширину из всех вершин $$$i$$$ с $$$mask = 0$$$. Теперь осталось научиться обновлять нашу $$$mask$$$.
Пусть мы стоим в вершине $$$i$$$ с артефактом $$$a[i]$$$. Тогда обозначим $$$new\_mask$$$ = $$$mask\ \mathtt{or}\ 2^{a[i]}$$$, то есть маска с добавленным артифактом $$$a[i]$$$. Попытаемся обновить ответ для $$$\mathtt{dp}[i][new\_mask]$$$ через $$$\mathtt{dp}[i][mask]$$$, после чего присвоим $$$mask = new\_mask$$$ (несложно понять, что нам надо выполнять такое присваивание в любом случае). Затем пройдемся по ребрам, исходящим из вершины $$$i$$$, и попробуем обновить ответ для $$$\mathtt{dp}[j][new\_mask]$$$. Ответом на задачу будет минимум по всем $$$\mathtt{dp}[i][2^k - 1]$$$. Если же мы не смогли посетить ни одну такую $$$mask$$$, то ответ на задачу равен $$$-1$$$. Итоговая асимптотика будет равна $$$\mathcal{O}(n \cdot 2^k \cdot \log(n \cdot 2^k))$$$.