Заметим, что после каждого запроса схема метро остается деревом. Тогда время, за которое можно пройти все метро и вернуться на начальную станцию составляет 2 * (количество ребер в дереве) минут. Но нам не нужно возвращаться на начальную станцию. В таком случае, если зафиксировать начальную и конечную станцию, то время за которое можно посетить все станции хотя-бы один раз составляет 2*(количество ребер в дереве) - (расстояние от начальной до конечной станции). Чтобы минимизировать эту величину, нужно выбрать начальную и конечную станцию так, чтобы расстояние между ними было максимальное. Такую величину величину еще называют диаметром дерева. Задача свелась к тому, что нам нужно уметь поддерживать количество ребер и диаметр в дереве после каждого запроса.

Научимся решать задачу, если у нас запросы только первого типа. Будем поддерживать концы диаметра дерева(пускай это будут вершина $a$ и $b$). Представим, что мы добавили вершину $c$. Тогда нашим новым диаметром станет либо $(a, b)$, либо $(a, c)$, либо $(b, c)$. Это следует из того, что если подвесить дерево за предок вершины $c$, то самой глубокой вершиной будет вершина $a$ или $b$(Доказательство этого факта остается за читателями). И тогда из алгоритма поиска диаметра дерева через два BFS, получаем вышеупомянутый результат.

Теперь мы заметим, что каждая станция имеет отрезок, на котором это станция существует. Заведем дерево отрезков, а в нодах будем хранить список станций(если нода отвечает за отрезок $[l, r]$, то все станции обязаны существовать на этом отрезке).
Сделаем обход по дереву обходу отрезков. Будем поддерживать количество ребер и текущий диаметр дерева. Перед тем, как зайти в ноду скопируем значения количества ребер и диаметра дерева из предка. Затем обновим эти параметры с учетом списка вершин. Как только мы окажемся в $i$ листе дерева отрезков, мы получим ответ на $i$ запрос.