Петар организует вечеринку по случаю своего дня рождения и планирует пригласить некоторых сотрудников из компании, где он работает генеральным директором. Каждый сотрудник, включая Петара, имеет уникальный номер от 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
Вы наверняка слышали легенду о Короле Артуре и Рыцарях Круглого Стола. Практически все версии этой истории указывают на то, что круглость Круглого Стола тесно связана с верой Артура в равенство среди рыцарей. Это ложь! На самом деле выбор Артура касательно формы стола вызван его детской травмой.
В реальности Артур был принужден убирать и мыть квадратные столы с юного возраста после того как на них играли в бирюльки. После соревнований по этой игре обычно на столе остается множество палочек, не касающихся друг друга. В духе соревнования, организаторы установили свод строгих правил для уборщиков. Точнее, палочки со стола должны быть убраны одна за другой путем их сдвига к ближайшему к уборщику краю стола. Они не должны вращаться и касаться других палочек в процессе перемещения.
В этой задаче представим стол на координатной плоскости как квадрат с противоположными вершинами в точках (0, 0) и (10000, 10000), где палочкам соответствуют прямые отрезки, лежащие внутри квадрата. Предположим, что Артур сидит у края стола, прилежащего к оси X. Тогда уборка палочек со стола сводится к передвижению их к оси X, покуда они не упадут со стола. Ваша задача - определить порядок уборки палочек со стола, который соответствует условиям из предыдущего абзаца.
Первая строка содержит единственное целое число N ( 1 ≤ N ≤ 5000 ) - количество палочек на столе. Каждая из следующих N строк содержит 4 целых числа x 1 , y 1 , x 2 , y 2 ( 0 ≤ x 1 , y 1 , x 2 , y 2 ≤ 10000 ), обозначающих крайние точки палочек.
В единственной строке выведите N целых чисел - номера палочек в том порядке, в котором они должны быть убраны со стола. Если существует несколько решений, выведите любое из них.
4 1 3 2 2 1 1 3 2 2 4 7 3 3 3 5 3
2 4 1 3
4 0 0 1 1 1 2 0 3 2 2 3 3 4 0 3 1
4 3 1 2
3 4 6 5 5 2 1 15 1 3 2 8 7
2 3 1
Ученые в тайной химической лаборатории в Хорватии изучают химические связи в недавно обнаруженном веществе инопланетного происхождения. Имеющаяся в распоряжении ученых порция вещества состоит из N молекул, соединенных между собой N - 1 ковалентными связями, и все молекулы объединены этими связями (не обязательно напрямую) в единую сеть.
Так как вещество нестабильное, в каждой молекуле регулярно возникают импульсы, перемещающиеся по веществу через существующие связи в обоих направлениях. Ученые собираются стабилизировать вещество, направив ковалентные связи (то есть, дав импульсам возможность путешествовать по ним между молекулами лишь в одном направлении). Показатель нестабильности вещества определяется длиной максимального пути, который может пройти импульс в нем, и ученые хотят сделать эту величину как можно меньше.
Помогите ученым создать вещество с минимальным показателем нестабильности, указав необходимое направление ковалентных связей.
Первая строка содержит одно целое число N ( 2 ≤ N ≤ 100000 ). Каждая из последующих N - 1 строк содержит по два целых числа a i и b i ( 1 ≤ a i , b i ≤ N ), которые показывают что молекулы с номерами a i и b i соединены ковалентной связью.
Выведите N - 1 строку, каждая из которых должна содержать 1 если ковалентная связь должна быть направлена от a i к b i или 0 в противном случае.
Решения, в которых N ≤ 20 , будут оцениваться в 30 баллов.
3 1 2 2 3
0 1
4 2 1 1 3 4 1
1 0 1
На родной планете Чубакки растет очень большое дерево, на ветках которого вуки строят свои домики. Чубакке стало интересно, как быстро можно попасть из некоторых домиков в другие. Вам придется ответить на несколько его вопросов, чтобы он вас отпустил.
Вам дано дерево с N вершинами порядка K , то есть каждая вершина дерева может иметь не более K потомков. Дерево создано по принципу "минимальной энергии": вершины в нем располагается на новом уровне только тогда, когда все места на предыдущем уровне (слева направо) заняты. В таком же порядке вершины дерева пронумерованы, начиная с 1.
Вам необходимо ответить на Q запросов вида " x y ", где ответом является расстояние (количество ребер в минимальном пути) в данном дереве между вершинами с номерами x и y .
Первая строка содержит три целых числа: N ( 1 ≤ N ≤ 10 15 ), K ( 1 ≤ K ≤ 1000 ) и Q ( 1 ≤ Q ≤ 100000 ). Каждая из следующих Q строк содержит пару чисел x y ( 1 ≤ x , y ≤ N , x ≠ y ) - запросы, описанные в условии.
Выведите Q строк, в каждой из которых одно целое число - ответ на соответствующий запрос.
Решения, работающие при 1 ≤ N , Q ≤ 1000 , будут оцениваться в 20 баллов. Решения, работающие при 1 ≤ N , Q ≤ 100000 , будут оцениваться в 50 баллов.
7 2 3 1 2 2 1 4 7
1 1 4
9 3 3 8 9 5 7 8 4
2 2 3
Давным-давно в одной далекой-далекой галактике, было N планет. Также было N - 1 межпланетных магистралей, соединявших между собой все планеты (не обязательно напрямую). Иными словами, сеть планет и магистралей образовывала дерево. Кроме того, каждая магистраль имеет свой показатель интересности, заданный неотрицательным целым числом. Пара планет ( A , B ) называется скучной, если выполняются следующие условия:
1. A и B - различные планеты.
2. В действующей сети межпланетных магистралей существует путь между A и B .
3. Побитовый XOR показателей интересности всех магистралей в этом пути равен 0.
Ныне в галактике правит злой император, и он планирует использовать Силу, чтобы уничтожить все межпланетные магистрали в определенном порядке. Для того, чтобы спасти вселенную от гибели, вам необходимо определить количество пар скучных планет и после каждого разрушения вновь подсчитывать эту величину.
Первая строка содержит одно целое число N ( 1 ≤ N ≤ 100000 ). Каждая из следующих N - 1 строк содержит три целых числа A i , B i , Z i ( 1 ≤ A i , B i ≤ 100000 , 0 ≤ Z i ≤ 1000000000 ), которые означают, что планеты с номерами A i и B i соединены магистралью с показателем интересности Z i . Последняя строка содержит N - 1 число: перестановку натуральных чисел от 1 до N - 1 , отражающую порядок уничтожения магистралей (если i -е число в строке равно j , то император уничтожит дорогу между планетами A j и B j на i -м шаге).
Выведите N строк, в k -й строке выведите одно число - количество пар скучных планет после уничтожения k - 1 дорог.
Решения, работающие при N ≤ 1000 , будут оцениваться в 20 баллов. Решения, работающие в случае когда показатель интересности всех путей равен 0, будут оцениваться не менее чем в 30 баллов.
2 1 2 0 1
1 0
3 1 2 4 2 3 4 1 2
1 0 0
4 1 2 0 2 3 0 2 4 0 3 1 2
6 3 1 0