--->
2 задач
<---
Петар организует вечеринку по случаю своего дня рождения и планирует пригласить некоторых сотрудников из компании, где он работает генеральным директором. Каждый сотрудник, включая Петара, имеет уникальный номер от 1 до N и тип шуток, которые он рассказывает, V i . Также, каждый сотрудник в компании кроме Петара имеет ровно одного начальника. Так как Петар - генеральный директор компании, он имеет номер 1 и руководит всеми сотрудниками (не обязательно напрямую).
На вечеринке есть некоторые правила, которым должны отвечать все присутствующие: 1. На вечеринке не должно быть двух людей с одинаковым типом шуток. 2. Человек не может быть приглашен на вечеринку, если на нее не приглашен его прямой начальник. 3. Человек не может быть приглашен на вечеринку, если типы шуток, которые рассказывает он и его приглашенные подчиненные, не образуют последовательное множество.
Петар хочет знать, сколько возможных наборов типов шуток может быть на его вечеринке, если он пригласит людей в соответствии с вышеуказанными правилами.
Последовательное множество - такое множество, в котором, если отсортировать его по возрастанию, разность между соседними элементами будет равна 1. Например (3, 1, 2) и (5, 1, 2, 4, 3) - последовательные множества, а (2, 5, 3) - нет.
Первая строка содержит одно целое число N ( 1 ≤ N ≤ 10000 ). Вторая строка содержит N целых чисел V i - типы шуток, рассказываемые i -м человеком ( 1 ≤ V i ≤ 100 ). Каждая из следующих N - 1 строк содержит два целых числа A и B ( 1 ≤ A , B ≤ N ), обозначающих что сотрудник с номером A является прямым начальником сотрудника с номером B .
Выведите единственное число - количество возможных наборов типов шуток на вечеринке.
4 2 1 3 4 1 2 1 3 3 4
6
4 3 4 5 6 1 2 1 3 2 4
3
6 5 3 6 4 2 1 1 2 1 3 1 4 2 5 5 6
10
Мирко большой любитель шахмат и программирования, но обычные шахматы уже наскучили ему, поэтому он начал экспериментировать и придумал свою игру. Он взял шахматную доску с N рядами и N столбцами и расположил на ней K ладей. Игра Мирко следует таким правилам: 1. У каждой ладьи есть своя сила, заданная натуральным числом. 2. Ладья видит все клетки поля в своем ряду и своем столбце кроме той, на которой стоит сама. 3. Клетка считается атакованной в том случае, если побитовый XOR сил всех ладей, которые видят эту клетку, положителен. Изначально Мирко некоторым образом расположил ладьи на поле, и теперь собирается сделать P перемещений. Каждый раз он будет брать одну ладью и ставить ее на другую клетку поля (при этом ладья не обязательно будет перемещена вдоль ряда или столбца в котором она стоит). После каждого перемещения, определите сколько клеток на поле атакованы.
Первая строка содержит 3 целых числа N , K , P ( 1 ≤ N ≤ 1000000000 , 1 ≤ K , P ≤ 10000 ). Каждая из следующих K строк содержит 3 натуральных числа R i , C i , X i ( 1 ≤ R i , C i ≤ N , 1 ≤ X i ≤ 1000000000 ), которые обозначают что на клетке ( R i , C i ) стоит ладья с силой X i . Каждая из следующих P строк содержит 4 натуральных числа R 1 , C 1 , R 2 , C 2 ( 1 ≤ R 1, C 1, R 2, C 2 ≤ N ), которые означают что ладья, стоящая на клетке ( R 1, C 1 ), была передвинута на поле ( R 2, C 2 ). Гарантируется, что в момент перемещения на клетке ( R 1, C 1 ) есть ладья и что ни в какой момент времени на одной клетке нет двух и более ладей.
Выведите P строк, где в k -й строке записано единственное число - количество клеток поля, атакованных после первых k перемещений.
2 2 2 1 1 1 2 2 1 2 2 2 1 1 1 1 2
4 0
2 2 2 1 1 1 2 2 2 2 2 2 1 1 1 1 2
4 2
3 3 4 1 1 1 2 2 2 2 3 3 2 3 3 3 3 3 3 1 1 1 1 2 3 1 3 2
6 7 7 9