Деревья


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 39676. Бункеры
Темы: Хеш    Деревья   

Петя и Вася с упоением играют в шпионов. Сегодня они планируют, где будут 
расположены их секретные бункеры и штаб-квартира. 

Пока Петя и Вася решили, что им понадобится ровно n бункеров, которые для секретности будут пронумерованы числами от 1 до n. 
Некоторые из них будут соединены двусторонними тоннелями, причем для надежности и секретности по тоннелям можно будет попасть из любого бункера в любой единственным образом.
Петя и Вася даже решили, какие из бункеров будут соединены тоннелями, но выбрать, какой из них будет штаб-квартирой, они не могут. 
Мальчики хотят выбрать ее и разделить оставшиеся бункеры между собой таким образом, чтобы им досталось поровну бункеров к штаб-квартире вело бы ровно два тоннеля: один от бункера, принадлежащего Васе, другой - от бункера, принадлежащего Пете. 
                                                                                   
Уставший Петя пошел к себе домой, а утром Вася показал ему план, на котором бункеры были обозначены точками, а тоннели отрезками. 
Кроме того, Вася выбрал штаб-квартиру таким образом, что нарисованный им план был симметричен относительно прямой, проходящей через точку, которая соответствовала штаб-квартире.
 
Хотя Петя почти сразу показал Васе, что тот ошибся и не нарисовал половину бункеров, ему стало интересно, можно ли выбрать штаб-квартиру и нарисовать такой симметричный план.

Входные данные:
В первой строке входного файла находится одно целое число n (1 <= n <= 105) - количество бункеров. 
В следующих n - 1 строках находится по два целых числа ui и vi (1 <= ui, vi <= n, ui ≠ vi) - номера бункеров, которые соединяет i-ый тоннель. 
Гарантируется, что между любыми двумя бункерами существует единственный путь.

Выходные данные:
В выходной файл выведите "YES", если можно выбрать штаб-квартиру и нарисовать такой план, или "NO" если это невозможно.

Примеры:
 

Входные данные Выходные данные
2
1 2		 NO
3
1 2
2 3		 YES

ID 39670. Странный сон Константина
Темы: Хеш    Бор    Деревья    Деревья   

Однажды Константин, поучаствовав в очередной, уже 13-ой по счету международной олимпиаде, возвращался на поезде домой. Он как всегда сидел и размышлял о смысле жизни, попутно решая задачи по программированию. Через некоторое время Константин задремал, но вот беда, для того, чтобы проснуться, он должен решить всплывшую у него в голове задачу, не дающую ему покоя!

В этот раз Константину приснилось дерево, изначально состоящее всего из одной вершины с номером 1. В поставленной им задаче к дереву постепенно добавлялись новые вершины. В i-ую секунду в дерево добавлялась вершина с номером i+1, которая подвешивалась в качестве сына к вершине pi, а на ребре между вершинами i+1 и pi записывалась буква ci.

Каждому пути из корня дерева до вершины v соответствует некоторая строка, получающаяся путем выписывания символов, записанных на ребрах текущего пути в порядке следования от корня к вершине v. Перед Константином стояла нелегкая на первый взгляд задача - после каждого добавления новой вершины посчитать количество уникальных строк, начинающихся в корне дерева (вершине с номером 1), и заканчивающихся в какой-либо другой вершине. 

В своем сне Константин вовсе не гений, поэтому решить эту задачу сам он не в силах. Помогите Константину решить задачу и тем самым проснуться.

Входные данные:
В первой строке записано число n - количество запросов на добавление новой вершины в дерево (1 <= n <= 300000).
В следующих n строках описаны запросы добавления вершин. i-ый запрос описывается параметрами pi (1 <= pi <= i) и ci, которые означают, что добавленная вершина с номером i+1 подвешивается к вершине с номером pi в качестве потомка, а на полученном ребре записывается символ ci - строчная буква латинского алфавита.

Выходные данные:
Выведите n строк. В i-ой строке выведите ответ на задачу Константина после добавления i+1-ой вершины.

Примеры:
 

Входные данные Выходные данные
2
1 b
2 p		 1
2
3
1 o
1 o
2 j		 1
1
2

ID 44645. Высота дерева
Темы: Деревья   

Реализуйте бинарное дерево поиска для целых чисел. Программа получает на вход последовательность целых чисел и строит из них дерево. Элементы в деревья добавляются в соответствии с результатом поиска их места. Если элемент уже существует в дереве, добавлять его не надо. Балансировка дерева не производится.


Входные данные

На вход программа получает последовательность натуральных чисел. Последовательность завершается числом 0, которое означает конец ввода, и добавлять его в дерево не надо.


Выходные данные

Выведите единственное число – высоту получившегося дерева.

Пример соответствует следующему дереву:

 
Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0
 
4

ID 44646. Количество элементов в дереве
Темы: Деревья   

Подсчитайте количество элементов в получившемся дереве и выведите это количество.


Входные данные

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.


Выходные данные

Выведите ответ на задачу.

 
Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0
 
9

ID 44647. Выведи листья
Темы: Деревья   

Для полученного дерева выведите список всех листьев (вершин, не имеющих потомков) в порядке возрастания.


Входные данные

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.


Выходные данные

Выведите ответ на задачу.

 
Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0

1
4
6
8

ID 44648. Выведи развилки
Темы: Деревья   

Для полученного дерева выведите список всех вершин, имеющих по два ребёнка, в порядке возрастания.


Входные данные

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит. Постройте по этой последовательности дерево.


Выходные данные

Выведите ответ задачи.

 
Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0
 
3
5
7

ID 44649. Сбалансированность
Темы: Деревья   

Дерево называется сбалансированным, если для любой его вершины высота левого и правого поддерева для этой вершины различаются не более чем на 1.

Входные данные
Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит. Постройте дерево, соответствующее данной последовательности.

Выходные данные
Определите, является ли дерево сбалансированным, выведите слово YES или NO.
 
Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0
 
YES

ID 44772. Второй максимум в дереве
Темы: Деревья   

Выведите второй по величине элемент в построенном дереве. Гарантируется, что такой найдется.


Входные данные

Дана последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.


Выходные данные

Выведите ответ на задачу.

 
Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0
 
8

ID 44773. Обход дерева
Темы: Деревья   

Выведите все элементы полученного дерева в порядке возрастания.


Входные данные

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит. По данной последовательности требуется построить дерево.


Выходные данные

Выведите ответ на задачу.

 
Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0
 
1
2
3
4
5
6
7
8
9

ID 44774. Ветки дерева
Темы: Деревья   

Для полученного дерева выведите список всех вершин, имеющих только одного ребёнка, в порядке возрастания.


Входные данные

Вводится последовательность целых чисел,оканчивающаяся нулем. Построить по ней дерево.


Выходные данные

Выведите список требуемых вершин.

 

Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0
 
2
9

ID 44985. Бинарное дерево (вставка, поиск)
Темы: Деревья   

Напишите программу, которая будет реализовывать действия в бинарном дереве поиска «вставить» и «найти» (по значению). Программа должна обрабатывать запросы трёх видов:

ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».

SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

 

Входные данные

В каждой строке входных данных записан один из запросов ADD n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

 

Выходные данные

Для каждого запроса выводите ответ на него. Для запросов ADD и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:
 

template void print_tree(Node *p, int level)

{

  if(p==NULL)

    return;

  print_tree(p->left, level+1);

  for(int i=0; i < level; i++)

    cout << ".";

  cout <<  p->data << endl;

  print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

 
Примеры
№ Входные данные Выходные данные
1 
ADD 2
ADD 3
ADD 2
SEARCH 2
ADD 5
PRINTTREE
SEARCH 7
 
DONE
DONE
ALREADY
YES
DONE
2
.3
..5
NO

ID 44987. Бинарное дерево (вставка, поиск, удаление)
Темы: Деревья   

Напишите программу, которая будет реализовывать действия в бинарном дереве поиска «вставить», «удалить» и «найти» (по значению). Программа должна обрабатывать запросы четырёх видов:

ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».

DELETE n — если указанное число есть в дереве, удалять его и выводить слово «DONE», если нет — оставлять дерево как было и выводить слово «CANNOT». При удалении элемента, имеющего два сына, обязательно обменивать значение с максимальным элементом левого поддерева.

SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

 

Входные данные

В каждой строке входных данных записан один из запросов ADD n или DELETE n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

 

Выходные данные

Для каждого запроса выводите ответ на него. Для запросов ADD, DELETE и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:

template void print_tree(Node *p, int level)

{

  if(p==NULL)

    return;

  print_tree(p->left, level+1);

  for(int i=0; i < level; i++)

    cout << ".";

  cout <<  p->data << endl;

  print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

 
Примеры
№ Входные данные Выходные данные
1 
ADD 2
ADD 7
ADD 5
PRINTTREE
ADD 5
DELETE 3
ADD 0
PRINTTREE
DELETE 7
PRINTTREE
 
DONE
DONE
DONE
2
..5
.7
ALREADY
CANNOT
DONE
.0
2
..5
.7
DONE
.0
2
.5
 
ID 44989. Переворот
Темы: Деревья   

Дан массив. Надо научиться обрабатывать два типа запросов.

* 1 L R - перевернуть отрезок [L,R]

* 2 L R - найти минимум на отрезке [L,R]


Входные данные

Первая строка файла содержит два числа n, m. (1<=n,m<=105) Во второй строке находится n чисел ni (1<=ai<=109) - исходный массив. Остальные m строк содержат запросы, в формате описанном в условии. Для чисел L, R выполняется ограничение (1<=L<=R<=n).


Выходные данные

На каждый запрос типа 2, во входной файл выведите ответ на него, в отдельной строке.

 
Примеры
№ Входные данные Выходные данные
1 
10 7
5 3 2 3 12 6 7 5 10 12
2 4 9
1 4 6
2 1 8
1 1 8
1 8 9
2 1 7
2 3 6
 
3
2
2
2

ID 44992. Range Minimum Query
Темы: Деревья   

Компания Giggle открывает свой новый офис в Судиславле, и вы приглашены на собеседование. Ваша задача — решить поставленную задачу.

Вам нужно создать структуру данных, которая представляет из себя массив целых чисел. Изначально массив пуст. Вам нужно поддерживать две операции:

  • запрос: «? i j» — возвращает минимальный элемент между i-ым и j-м, включительно;
  • изменение: «+ i x» — добавить элемент x после i-го элемента списка. Если i=0, то элемент добавляется в начало массива.

Конечно, эта структура должна быть достаточно хорошей.


Входные данные

Первая строка входного файла содержит единственное целое число n — число операций над массивом (1<=n<=200000). Следующие n строк описывают сами операции. Все операции добавления являются корректными. Все числа, хранящиеся в массиве, по модулю не превосходят 109.


Выходные данные

Для каждой операции в отдельной строке выведите её результат.


Комментарий к примеру тестов

Нижеследующая таблица показывает процесс изменения массива из примера.
Операция Массив после её выполнения
изначально пуст
+ 0 5 5
+ 1 3 5, 3
+ 1 4 5, 4, 3
+ 0 2 2, 5, 4, 3
+ 4 1 2, 5, 4, 3, 1

 

Примеры
№ Входные данные Выходные данные
1 
8
+ 0 5
+ 1 3
+ 1 4
? 1 2
+ 0 2
? 2 4
+ 4 1
? 3 5
 
4
3
1

ID 44997. Вычисление простого выражения
Темы: Деревья   

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются только целые числа и знаки арифметических операций (+-*/). Результат операции деления – целое число.

 

Входные данные

На вход программы поступает символьная строка, содержащая правильную запись арифметического выражения.

 

Выходные данные

Программа должна вывести значение переданного ей выражения как целое число.

 
Примеры
№ Входные данные Выходные данные
1 
125-6-73/5*8
 
7

ID 44998. Вычисление простого выражения со скобками
Темы: Деревья   

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются только целые числа, знаки арифметических операций (+-*/) и скобки произвольной вложенности. Результат операции деления – целое число.

 

Входные данные

На вход программы поступает символьная строка, содержащая правильную запись арифметического выражения, возможно, со скобками.

 

Выходные данные

Программа должна вывести значение переданного ей выражения как целое число.

 
Примеры
№ Входные данные Выходные данные
1 
(5+20)*(98-34)/(5*8-23)
 
94

ID 44999. Вычисление выражения с функциями
Темы: Деревья   

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются целые числа, знаки арифметических операций, круглые скобки и вызовы функций ( sin , cos , abs , sqrt ). Результат операции деления – вещественное число.

 

Входные данные

На вход программы поступает символьная строка, содержащая правильную запись арифметического выражения.

 

Выходные данные

Программа должна вывести значение переданного ей выражения как вещественное число. При выводе результата нужно оставить 3 знака в дробной части числа.

 
Примеры
№ Входные данные Выходные данные
1 
12+cos(sqrt(12+sin(2)))
 
11.100

ID 45000. Вычисление выражения с вычислениями
Темы: Деревья   

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются целые числа, знаки арифметических операций, круглые скобки, вызовы функций ( sin , cos , abs , sqrt ) и имена переменных (только однобуквенные). Результат операции деления – вещественное число.

 

Входные данные

Первая строка содержит правильную запись арифметического выражения. В следующих нескольких строках записаны значения всех переменных, использованных в выражении. Каждая из этих строк имеет формат:

<имя переменной>=<значение>

Каждое имя переменной состоят из одной строчной буквы латинского алфавита.

 

Выходные данные

Программа должна вывести значение переданного ей выражения как вещественное число. При выводе результата нужно оставить 3 знака в дробной части числа.

 
Примеры
№ Входные данные Выходные данные
1 
cos(z+abs(sqrt(r*sin(x+4))))
r=5
z=10
x=3
 
0.729

ID 24765. Воздушные потоки
Темы: Деревья    Наименьший общий предок    Разреженные таблицы (sparse table)    Структуры данных    Префиксные суммы(минимумы, ...)   

Колобок ушёл от бабушки и поехал путешествовать. Неожиданно для себя он забрёл в страну Ивэнлэнд. Первые трудности встали на его пути: Колобка и вход в страну отделял огромный ров с водой, которая, как известно, не очень хорошо влияет на нашего героя. К счастью, повсюду рас- положены воздушные потоки, которые могли поднимать того, кто на них встает, на определённую высоту. Страна не просто так названа Ивэнлэнд, поэтому все высоты, на которые могут поднять героя воздушные потоки — это чётные числа.

Представим воздушные потоки как массив h[1..n] из n натуральных чисел — высот потоков. Для каждого 1 ≤ i ≤ n посчитаем G[i] — индекс ближайшего элемента слева, строго большего h[i]. Более формально, g[i] = max{j | j < i и h[j] > h[i]}. Если i = 1 или до h[i] нет ни одного элемента больше него, то G[i] считается равным 0.

Колобок считает, что оптимальность расположения воздушных потоков определяется суммой


Чем меньше сумма, тем расположение оптимальнее. Всё, что может сейчас сделать Колобок — это увеличить высоту одного из воздушных потоков не более чем на m. После этого действия высота потока должна остаться целым числом, но может, если необходимо, стать и нечётной.

Помогите Колобку сделать оптимальное изменение, которое позволит добиться, чтобы сумма S(h), описанная выше, после проделанного действия была минимальна.

Формат входного файла
В первой строке входного файла даны числа n, m (1 ≤ n ≤ 105 , 1 ≤ m ≤ 109 ) — количество воздушных потоков и максимальное значение, на которое можно увеличить высоту одного из них. Во второй строке даны высоты воздушных потоков h[i] (1 ≤ h[i] ≤ 109 ). Гарантируется, что все высоты — чётные числа.

Формат выходного файла
В единственной строке выходного файла выведите одно целое число — минимальную искомую сумму.
 

Ввод Вывод
3 100
4 2 6		 4
3 2
4 2 6		 5
3 10
2 2 2		 4

ID 24761. Путь в никуда
Темы: Деревья    Деревья    Структуры данных    Разреженные таблицы (sparse table)    Бинарный поиск    Префиксные суммы(минимумы, ...)   

Колобку снится странный сон.
В нём Колобок находится на клетчатом поле размера n × m в клетке с координатами (x, y).
Изначально Колобок смотрит вдоль положительного направления оси X. Затем он начинает идти по полю со следующей закономерностью:
• Пройти на одну клетку вперед. Повернуть на 90o вправо.
• Пройти на одну клетку вперед. Повернуть на 90o вправо.
• Пройти на две клетки вперед. Повернуть на 90o вправо.
• Пройти на две клетки вперед. Повернуть на 90o вправо.
• Пройти на три клетки вперед. Повернуть на 90o вправо.
• Пройти на три клетки вперед. Повернуть на 90o вправо.
• Пройти на четыре клетки вперед. Повернуть на 90o вправо.
• И так далее...

Движение продолжается до тех пор, пока Колобок не выйдет за границы поля. После этого Колобок просыпается.

Утром Колобок решил проанализировать свой сон. Он догадался, что в каждой клетке он был максимум один раз, но никак не может вспомнить, сколько клеток он посетил. Колобок просит вас написать программу, которая посчитает количество посещённых им клеток.




Формат входного файла
В первой строке входного файла находятся два натуральных числа n, m (1 ≤ n, m ≤ 109 ) — размеры доски вдоль оси X и оси Y соответственно. Во второй строке находятся два натуральных числа x, y (1 ≤ x ≤ n; 1 ≤ y ≤ m) — координаты стартовой позиции колобка.

Формат выходного файла
В выходной файл выведите одно число — количество клеток, посещенных Колобком во сне.
 

Вывод Ввод
7 6
3 4		 36
2 2
1 1		 2
2 2
1 2		 4

Комментарий
На рисунке наглядно показан первый пример.
 
ID 30710. Гномы и Одинокая гора
Темы: Обход в глубину    Применение обхода в глубину    Применение обхода в глубину    Обход в глубину    Деревья   

Гномы продолжают искать золото предков в недрах Одинокой горы. Недра Одинокой горы представляют собой n пещер, некоторые из которых соединены двусторонними переходами. При этом из каждой пещеры в любую другую можно попасть по переходам, причем это можно сделать единственным способом.

Гномы разделились на два отряда, которые начали свои поиски с пещер u0 и v0, соответственно. Гномы каждого из отрядов перемещаются вместе. На обследование пещеры у отряда гномов уходит ровно одна минута, после чего каждый отряд быстро перемещается по переходу в одну из соседних пещер. При этом гномы никогда не заходят в пещеру, если они или другой отряд в ней уже побывали. Оба отряда никогда не заходят в одну и ту же пещеру. Если хотя бы один из отрядов гномов не может переместиться в соответствии с этими правилами, оба отряда сразу прекращают поиски сокровищ.

Чтобы как можно лучше обследовать недра Одинокой горы, гномы хотят, чтобы поиски продолжались как можно дольше. По заданной карте пещер в Одинокой горе и начальному положению отрядов гномов определите, какое максимальное время могут продолжаться поиски сокровищ.

Формат входных данных
В первой строке число n (2 ≤ n ≤ 200 000) — число пещер в Одинокой горе. В следующих n−1 строках заданы переходы между пещерами. В каждой строке записаны номера двух пещер v и u, соединенных переходом (1 ≤ v, u ≤ n). В следующей строке заданы номера пещер v0 и u0, в которых исходно находятся два отряда гномов (1 ≤ v0, u0 ≤ n, v0 != u0).

Формат выходных данных
Выведите максимальное число минут, которое могут продолжаться поиски сокровищ.
 

Ввод Вывод Пояснение
6
1 2
2 3
3 4
4 5
5 6
4 5		 2
8
1 2
2 3
3 4
2 5
5 6
3 7
7 8
1 8		 4

ID 33124. Мониторинг труб
Темы: Деревья    Алгоритмы на графах    Строки    Динамическое программирование   

Газораспределительная система одного региона устроена следующим образом. Она
содержит n узлов, пронумерованных от 1 до n, некоторые узлы соединены односторонними
трубами. Узел с номером 1 соответствует центральному газохранилищу.
Система узлов описывается числами от p2, p3, …, pn. Для всех i от 2 до n узел с
номером pi соединен односторонней трубой с узлом i, газ по этой трубе передается от узла pi
к узлу i. Известно, что возможно доставить газ по трубам от центрального газохранилища до
любого узла системы (возможно, с использованием промежуточных узлов). В системе
используются трубы различных типов, тип трубы обозначается буквой английского алфавита
от «a» до «z». Труба, соединяющая узел pi с узлом i, имеет тип ci.
Для проверки качества труб используется специальный робот. Он помещается в
систему труб в одном из узлов и перемещается по трубам, каждый раз проверяя трубу, по
которой он перемещается. Робот может перемещаться по трубам только в том же
направлении, в котором по трубе передается газ. Совершив одно или несколько
перемещений по трубам между узлами, робот извлекается из системы труб.
Каждый запуск робота должен соответствовать одной из m заданных спецификаций,
пронумерованных от 1 до m. Спецификация с номером t представляет собой строку st,
состоящую из строчных букв английского алфавита. Запуск соответствует спецификации st,
если количество перемещений робота по трубам во время запуска совпадает с длиной st, и
для всех j от 1 до длины st на j-м шаге робот перемещается по трубе, тип которой совпадает с
st[j] —символом на позиции j в спецификации.
Если запуск робота соответствует спецификации с номером t, то стоимость этого
запуска составляет wt. Оператору системы необходимо проверить все трубы, для этого
можно запускать робот несколько раз. Каждый раз выбирается спецификация и маршрут
робота по трубам, соответствующие выбранной спецификации. Необходимо проверить все
трубы так, чтобы суммарная стоимость запусков робота для проверки качества труб была
минимальна. Одну и ту же трубу можно проверять несколько раз.
Требуется написать программу, которая по описанию системы труб и списку
спецификаций определяет минимальную суммарную стоимость запусков робота, в
результате которых все трубы будут проверены, а также список необходимых для этого
запусков (по требованию).
 
Формат входных данных
В первой строке входных данных находятся три целых числа n, m и t — количество
узлов системы труб, количество спецификаций запусков робота и параметр, указывающий,
требуется ли вывести список запусков робота или только их минимальную суммарную
стоимость (1 ≤ n ≤ 500, 1 ≤ m ≤ 105, t равно 0 или 1).
В последующих (n – 1) строках содержится информация о трубах, (i – 1)-я из этих
строк содержит разделенные пробелом значения pi и ci, где pi — целое число, задающее
номер узла, из которого ведет труба в i-й узел, а ci — строчная буква английского алфавита,
задающая тип этой трубы (1 ≤ pi ≤ i – 1).
В последующих m строках содержится информация о спецификациях, i-я из этих
строк содержит разделенные пробелом целое число wi — стоимость запуска робота в
соответствии с этой спецификацией, и состоящую из строчных букв английского алфавита
строку si — саму спецификацию (1 ≤ wi ≤ 109). Суммарная длина строк si не превышает 106.
 
Формат выходных данных
Первая строка выходных данных должна содержать одно число — минимальную
суммарную стоимость запусков робота, в результате которых все трубы будут проверены.
Если проверить все трубы невозможно, требуется вывести «–1».
Если t = 0, то больше ничего выводить не требуется.
Если t = 1 и проверить трубы возможно, то далее следует вывести список описаний
запусков робота. В этом случае вторая строка выходных данных должна содержать
число k — количество запусков робота, которое необходимо выполнить для проверки труб. В
следующих k строках необходимо вывести по три целых числа ai, bi и ci — номер узла, в
котором начинается запуск, номер узла, в котором заканчивается запуск, и номер
спецификации, которой соответствует запуск.
Если оптимальных способов проверки несколько, требуется вывести любой из них.
 
Ввод Вывод
3 3 0
1 a
2 b
3 a
4 b
2 a
 6
7 3 1
1 a
2 a
3 b
3 b
1 b
6 b
3 aab
5 b
2 ab
15
4
1 4 1
2 5 3
1 6 2
6 7 2
 
 
Пояснение к примеру
Система труб, заданная во втором примере входных данных, и оптимальный способ
проверки всех труб для этого случая приведены на рисунке ниже.
 


 
Необходимо обратить внимание на следующие моменты:
- трубу можно проверять несколько раз, так в приведенном примере дважды
проверена труба из узла 2 в узел 3;
- одну и ту же спецификацию разрешается использовать несколько раз, в
приведенном примере вторая спецификация используется дважды, для
проверки труб из узла 1 в узел 6 и из узла 6 в узел 7;
- робот может перемещаться по трубам только в том же направлении, по
которому по трубе передается газ, спецификацию «ab» нельзя использовать
для проверки труб по маршруту 2→1→6, так как робот не может
переместиться из узла 2 в узел 1.
ID 38805. Breaking News
Темы: Деревья    Обход в глубину   

Жизнь завода по производству олимпиадных задач монотонна и однообразна: каждый день происходит одно и то же, вечера похожи как две снежинки и каждое утро всё начинается сначала - ничего не меняется на заводе по производству олимпиадных задач.
В частности, давно известно, когда в течение дня пара сотрудников встречается между собой.
При встрече сотрудники делятся друг с другом новостями.
Утром перед работой сотрудник номер 1 узнал нежелательную новость. Конечно же, он делится с ней при встрече со всеми остальными сотрудниками и они тоже узнают новость и начинаются делиться ей с другими. Если встречаются два сотрудника и один из них знает новость, то начиная с этого момента второй из них также знает новость. Ни один сотрудник не может встречаться с двумя или более сотрудниками одновременно (из соображений секретности). Пара сотрудников может встречаться несколько раз в течение дня.
Вы можете помешать ровно одной встрече за весь день. Выберите такую встречу, отмена которой приведёт к тому, что как можно меньше сотрудников завода узнают новость.

Входные данные
В первой строке входного файла задано два целых числа N (2 ≤ N ≤ 1000) и D (1 ≤ D ≤ 100000) — количество сотрудников и встреч соответственно. В следующих D строках заданы описания встреч. Каждое описание встречи состоит из трех
чисел Ai, Bi и Ti (1 ≤ Ai, Bi ≤ N, 1 ≤ Ti ≤ 109) — пара номеров сотрудников и время встречи.

Выходные данные
Выведите описание встречи, которую необходимо отменить в том же формате, который используется во входных данных. Если ответов несколько — выведите любой.

Примеры
№ Входные данные Выходные данные
1 4 5
2 3 1
1 2 4
4 2 110
2 3 5
3 4 4		 1 2 4