1493: Армія
Перегляд у форматі PDFВ армiї ~N~ вiйськових. Вiйськовi пронумерованi вiд 1 до ~N~ . У кожного вiйськового є один безпосереднiй командир. Командир командира є також командиром для цього вiйськового. Отже, у кожного вiйськового може бути один або бiльше командирiв, але лише один безпосереднiй командир. В якостi вправи для визначення ефективностi армiї було розроблено наступне навчання, яке вам треба реалiзувати у своїй програмi.
Задається список наказiв. Кожен наказ має форму: <~Type~><пропуск><~Id~>, де ~Type~ - 1, 2 або 3, а ~Id~ - це число ~S~ ~(1 \le S \le N )~, яке вказує на вiйськового пiд номером ~S~.
Iснує три типи наказiв:
1: Усi вiйськовi, у яких S є одним iз командирiв виконують команду ʼПiдйомʼ.
2: Усi вiйськовi, у яких S є одним iз командирiв виконують команду ʼВiдбiйʼ.
3: Потрiбно порахувати та вивести кiлькiсть вiйськових, якi не сплять, та у яких ~S~ є одним iз командирiв.
Серед усiх вiйськових є один, який не має жодного командира. Вiн - командувач армiї. На початку всi вiйськовi несуть службу (тобто не сплять).
Обмеження
~1 \le N \le 10^5~
~1 \le Q \le 10^5~
~1 \le Type \le 3~
~1 \le S \le N~
Формат вхідних даних
Перший рядок мiстить ~N~ - кiлькiсть вiйськових.
Наступний рядок мiстить ~N~ цiлих чисел, якi вказують на безпосереднього командира i-го вiйськового. Командувач армiї буде позначений числом 0.
Третiй рядок мiстить ~Q~, кiлькiсть наказiв.
Кожен з наступних ~Q~ рядкiв мiстить наказ: два цiлi числа, тип наказу та ~S~.
Формат вихідних даних
Для кожного наказу 3-го типу виведiть кiлькiсть вiйськових, якi не сплять, та у яких ~S~ є одним iз командирiв.
Приклад вхідних даних
3
2 0 1
3
3 1
2 1
3 1
Приклад вихідних даних
1
0
Пояснення
Є лише один вiйськовий, у якого 1 є командиром, тобто вiйськовий 3. Отже, вiдповiдь першого наказу 3-го типу - 1. Пiсля наказу ʼ2 1ʼ всi солдати, у яких 1 є одним iз командирiв (тут, лише вiйськовий 3) пiдуть спати. Тому вiдповiдь наступного наказу ʼ3 1ʼ - 0.
Коментарі
на пайтон достатньо часу?
не тестував, добавлю, подивимося що з того вийде