ПОМОГИТЕ РЕШИТЬ ЗАДАЧУ! Lessmeaning и Ferume владеют компанией Kilobytes For Universe. В компании n работников, пронумерованных от 1 до n, каждый из которых может быть - вопрос №2655028

директором одного или нескольких других работников (а может и не быть директором), и у каждого работника (кроме работника с номером 1) существует ровно один директор, у работника номер 1 нет директоров. У каждого из работников есть кабинет, и каждый из них может провести посетителя в кабинеты своих непосредственных подчиненных или ко своему непосредственному директору (то есть работник u может провести к работнику v тогда и только тогда когда u директор v или v директор u). Владельцы в обеденный перерыв играют в такую игру. Lessmeaning говорит, если бы я стоял в кабинете работника u и прошел бы по кратчайшему маршруту до кабинета работника v, увольняя каждого работника, в кабинет которого я попаду, то сколько бы главных директоров осталось в компании? (Маршрут является кратчайшим, если количество кабинетов в нем минимальное из всех возможных). Главный директор — работник, у которого нет директоров (обратите внимание — главный директор может не быть директором вовсе). Ferume смог бы легко отвечать на вопросы Lessmeaning, но в компании происходят реальные изменения — увольняют целые департаменты.У понятия департамент работника v индуктивное определение. Это группа работников, для которой выполнены следующие условия: 1) работник v входит в эту группу; 2) все работники, у которых директор входит в департамент работника v, также входят в департамент работника v; Более формально происходит q событий типа 1 u v и 2 v: 1 u v — означает, что Lessmeaning загадал загадку, на которую Ferume должен дать ответ; 2 v — означает, что уволены все работники из департамент работника v; Помогите Ferume решить все загадки Lessmeaning. Все события даны в хронологическом порядке. В качестве ответа на задачу нужно вывести все ответы на загадки. Важное замечание: в начальный момент все работники входят в департамент работника 1 (то есть граф зависимостей представляет собой корневое дерево). Входные данные В первой строке дано одно целое число n — количество работников (3 ≤ n ≤ 100000). В следующей n — 1 строке записано по два целых числа u и v (1 ≤ u, v ≤ n;u ≠ v), это значит, что работник u является директором работника v. В следующей строке дано число q (1 ≤ q ≤ 100000) — количество событий Следующие q строк вида 1 u v или 2 v. 1 ≤ u ≤ n, 1 ≤ v ≤ n, u ≠ v. Для запроса 2-го типа v ≠ 1. Выходные данные Выведите на каждое событие 1-го типа одно целое число число — ответ на запрос, в том порядке, в котором события следуют во входных данных.
12.11.17
0 ответов
Ответов пока нет

Виталий

от 100 p.
Читать ответы
Посмотреть всех экспертов из раздела Технологии > .Net/C#
Пользуйтесь нашим приложением Доступно на Google Play Загрузите в App Store