Заметим, что правильная система порталов всегда либо связна, либо содержит две компоненты связности, в каждой по одному входу. Доказательство этого внизу. Кстати,  первый вариант всегда невыгоден, потому что из него можно удалить одно ребро, чтобы получить второй вариант дешевле. Построим минимальный остов графа возможных порталов. Если он содержит больше двух компонент связности, на все запросы отвечаем -1. Если содержит две, то отвечаем -1 на запросы, у которых обе вершины в одной компоненте, и вес остова на все остальные запросы. Если компонента одна, нужно уметь разбивать дерево на два так, чтобы две указанные вершины остались в разных. Это делается удалением самого тяжелого ребра в дереве на пути между этими вершинами. Находить вес этого ребра можно, если заранее подвесить дерево и найти для каждой вершины прыжки вверх по степеням двойки (как для LCA) и для каждого прыжка еще вес самого тяжелого ребра на этом пути. Тогда нетрудно расширить алгоритм посика LCA вычислением максимального веса ребра на пути между вершинами.