printРабочее место участника

printЗадачи

1731. Дяди и тёти

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Профессор исторических наук Гречкин А.Ж. пишет работу по мифологии Древней Греции. Особенно его интересуют родственные связи между богами, образовавшиеся во время разрастания их запутанного родословного древа. В частности, профессора заинтересовал процесс подсчёта количества дядь и теть у некоторых из представителей Пантеона.
В данный момент у профессора Гречкина имеется большая база данных, хранящая информацию о родителях каждого из богов. Однако с компьютерами профессор дружит не сильно, поэтому работу по подсчёту родственников он предпочёл поручить вам.
Степени родства между богами определяются следующим образом:
Родными братьями (сестрами) называются боги, имеющие общего непосредственного родителя. Прародителями называются родители непосредственных родителей. Дядями (тетями) называются родные братья (сёстры) родителей.
При подсчете количества дядь и тёть из множества подходящих под определение богов исключаются:
  • сам изучаемый бог
  • его родители
  • его родные братья и сестры
  • его прародители
Количество оставшихся после этого исключения дядь и тёть является требуемым ответом.
В первой строке ввода записаны два числа `N` и `M` (`1\ ≤\ N\ ≤\ 40000`, `1\ ≤\ M\ ≤\ 4000` ) – количество богов в Пантеоне и количество изучаемых богов. В следующих `N` строках содержатся по 3 числа: `"id"` бога, `"id"` его матери и `"id"` отца. Если кто-то из родителей отсутствовал в системе известных нам родственных связей, то на соответствующей позиции вместо `"id"` стоит `-1`. Все `"id"` в диапазоне от 1 до 100000.
Каждая из следующих `M` строк содержит по одному числу – `"id"` бога, для которого необходимо посчитать суммарное количество дядь и теть.
Для каждого из `M` запросов требуется в отдельной строке напечатать единственное число – суммарное количество дядь и тёть у данного бога.

Пример ввода

9 3
1 5 7
2 -1 8
3 2 6
4 -1 6
5 -1 -1
6 5 7
7 -1 -1
8 -1 -1
9 -1 8
3
4
6

Пример вывода

2
1
0
Источник: Московская олимпиада школьников по информатике, 2011/12 учебный год
loading