Динамическое программирование на графах

Вы играете в игру «Бинарная Сила» и управляете персонажем, у которого есть 𝑑 = 2^𝑛 навыков, пронумерованных 1 до 𝑑. Эти навыки расположены на листьях полного двоичного дерева высоты 𝑛, изначально все навыки имеют уровень 1. Пример такого дерева для 𝑛 = 3 приведен на иллюстрации ниже.



После этого вы начинаете прокачивать навыки следующим образом.
• Навыки прокачиваются посредством заполнения двоичного дерева снизу вверх.
• Для очередной вершины дерева вы должны выбрать и записать в нее один из двух навыков, записанных в
непосредственных детях этой вершины (на рисунке из детей в родителя ведут стрелки).
• Уровнем навыка считается число вершин, в которых выбран этот навык.
Пример корректного распределения навыков по дереву для 𝑛 = 3 приведен ниже.


В этом примере первый навык имеет уровень 4, седьмой – уровень 3, четвертый и пятый – уровень 2, а второй, третий, шестой и восьмой не были прокачаны ни разу, поэтому остались на уровне 1.
Кроме прокачки персонажа, в игре есть 𝑚 различных квестов, с помощью которых можно получать монетки. Квесты активируются после того, как все дерево навыков было заполнено.
Квесты бывают трех типов:
1. «𝑙𝑒𝑠𝑠 𝑥𝑖 𝑘𝑖 𝑠𝑖» – вы получите 𝑠𝑖 монет, если уровень навыка с номером 𝑥𝑖 окажется строго меньше 𝑘𝑖 .
2. «𝑒𝑥𝑎𝑐𝑡 𝑥𝑖 𝑘𝑖 𝑠𝑖» – вы получите 𝑠𝑖 монет, если уровень навыка с номером 𝑥𝑖 окажется равен 𝑘𝑖 .
3. «𝑙𝑒𝑠𝑠 𝑥𝑖 𝑘𝑖 𝑠𝑖» – вы получите 𝑠𝑖 монет, если уровень навыка с номером 𝑥𝑖 окажется строго больше 𝑘𝑖 .
Так как монеты – очень ценный ресурс в игре «Бинарная Сила», вы хотите узнать максимальное количество монет, которое возможно получить с помощью имеющихся квестов после улучшения всех навыков.

Формат входных данных
Каждый тест состоит из нескольких независимых наборов входных данных. Первая строка содержит одно целое число 𝑡 – количество наборов входных данных (1 ≤ 𝑡 ≤ 10⁴). Далее следует описание наборов входных данных.
Каждый набор начинается со строки, содержащей два целых числа 𝑛 и 𝑚 – высоту дерева навыков и количество квестов соответственно (1 ≤ 𝑛 ≤ 15; 0 ≤ 𝑚 ≤ 50 000). Число навыков при этом равно 𝑑 = 2^𝑛.
Далее следуют 𝑚 строк, 𝑖-я из которых содержит четыре целых числа 𝑡𝑖, 𝑥𝑖, 𝑘𝑖, 𝑠𝑖 – тип квеста и его описание (1 ≤ 𝑡𝑖 ≤ 3; 1 ≤ 𝑥𝑖 ≤ 𝑑; 1 ≤ 𝑘𝑖 ≤ 𝑛; 1 ≤ 𝑠𝑖 ≤ 10⁹). Типы квестов следуют в том же порядке, в котором они перечислены в условии: 𝑡𝑖=1 соответствует квесту типа «𝑙𝑒𝑠𝑠», 𝑡𝑖 = 2 – квесту типа «𝑒𝑥𝑎𝑐𝑡» и 𝑡𝑖 = 3 – квесту типа «𝑚𝑜𝑟𝑒».
Гарантируется, что сумма 𝑑 по всем наборам входных данных не превосходит 2¹⁶ и сумма 𝑚 по всем наборам входных данных не превосходит 50 000

Формат выходных данных
Для каждого набора выходных данных в отдельной строке выведите единственное число – максимальное количество монет, которые можно заработать.
 

Однажды Юрик оказался в лесу у костра, где собрались \(n\) человек. Оказалось, что некоторые из них знакомы друг с другом. Для удобства пронумеруем людей целыми числами от \(1\) до \(n\). Обозначим как \(d_i\) количество людей, сидящих у костра, с которыми знаком \(i\)-й человек. Неожиданно оказалось, что два человека с номерами \(i\) и \(j\) (\(i \ne j\)) знакомы друг с другом тогда и только тогда, когда \(d_i = d_j\).

Вернувшись домой, Юрик задумался, какое минимальное количество пар людей могли быть знакомы, чтобы выполнялось это условие?

Формат входных данных
Единственная строка содержит одно целое число \(n\) (\(1 \le n \le 5\,000\)) — количество людей.

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

Рассмотрим первый пример из условия. Возможны следующие варианты:

1. Любые два человека знакомы друг с другом. В этом случае количество пар знакомых людей равно \(\frac{4 \cdot 3}{2} = 6\).

2. Некоторые три человека попарно знакомы друг с другом, четвертый человек не знаком ни с кем. В этом случае количество пар знакомых людей равно \(3\).

Приехав в Хоббитанию, белый маг Гэндальф принялся рассказывать Бильбо последние новости из Средиземья. Больше всего впечатлительного хоббита поразил рассказ о Большом огромном коллайдере - только представить себе гигантских размеров кольцо, зарытое под землей!

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

Бильбо хочет прокопать новые коридоры в норе, но так как копать будут только Фродо и сам Бильбо (не Гэндальф же!) , есть возможность прокопать только один или два новых коридора.

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

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

Входные данные
В первой строке входного файла содержится целое число n (3≤n≤100000) - число комнат в норе Бильбо.

В следующих n−1 строках содержатся по два целых числа - номера комнат, соединенных коридорами. Комнаты нумеруются от 1 до n.

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

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

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

Примечание
В первом примере коллайдер состоит из комнат с номерами 1, 2, 3 и 4 (именно в этом порядке), во втором примере - 1, 3, 2, 4.

Почти все Королевство Байтленд покрыто лесами и реками. Малые реки сливаются в более крупные реки, которые, в свою очередь, сливаются друг с другом; в конечном счете, все реки сливаются вместе в одну большую реку. Большая река впадает в море вблизи города Байттаун.

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

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

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

Задание
Напишите программу, которая:
<> * читает из стандартного ввода количество поселков, количество дополнительных пилорам, которые будут установлены, количество срубленных в каждом поселке деревьев и описание рек,
*вычисляет минимальную стоимость сплава деревьев после установки дополнительных пилорам,
*выводит результат в стандартный вывод.

Входные данные
Первая строка входных данных содержит два целых числа: n — количество поселков, не считая Байттауна (2 ≤ n ≤ 100), и k
 — количество дополнительных пилорам, которые будут установлены (1 ≤ k ≤ 50 и k ≤ n). Поселки нумеруются числами 1 , 2 ,...., n , а Байттаун имеет номер 0.

Каждая из последующих n строк содержит три целых числа, разделенных одним пробелом. Строка i + 1 содержит:

w_i — количество деревьев, срубаемых в поселке i за год (0 ≤ w_i ≤ 10 000),
v_i — ближайший поселок (либо Байттаун) вниз по реке от поселка i (0 ≤ v_i ≤ n),
d_i — расстояние (в километрах) по реке от поселка i до поселка v_i (1 ≤ d_i ≤ 10 000).
Гарантируется, что суммарная стоимость сплава всех деревьев к пилораме в Байттауне не превосходит 2 000 000 000 центов в год.
В 50% тестов число n не превосходит 20.

Выходные данные
Первая и единственная строка выходных данных должна содержать одно целое число: минимальную стоимость сплава (в центах).

Пояснения


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

Пилорамы должны быть установлены в поселках 2 и 3.

Сверхсекретный завод, расположенный высоко в горах, занимается изготовлением новейших систем контроля торсионных полей – нанокристаллов. Нанокристалл состоит из нескольких атомов, некоторые из которых попарно связаны сверхпрочными торсионными связями.

Нанокристалл стабилен, если между любыми двумя его атомами можно построить соединяющую их цепочку связей, возможно с использованием других атомов. Например, из четырех атомов A, B, C и D, в котором между собой связаны пары A - B, A - C, B - C и B - D, стабилен. Если же, например, в нанокристалле из данных четырех атомов связаны только пары A - B и C - D, то кристалл нестабилен, поскольку, например, A и C не соединены никакой цепочкой связей.

Для любой пары атомов стабильного нанокристалла определена их взаимная удаленность – минимальная длина цепочки из связей, которая их соединяет. Например, рассмотрим описанный выше нанокристалл. Взаимная удаленность атомов A и B равна единице (они соединены напрямую), а взаимная удаленность C и D равна двум (они соединены цепочками C - B - D и C - A - B - D, длина кратчайшей цепочки равна двум).

Важнейшей характерикой стабильного нанокристалла является его емкость. Емкость нанокристалла равна сумме взаимных удаленностей всех пар его атомов. Например, емкость нанокристалла равна 8.

Недавно на завод поступил заказ – разработать стабильный нанокристалл заданной емкости c. При этом как число атомов в нанокристалле, так и число связей может быть произвольным. Помогите ученым разработать такой кристалл!

Входные данные
На вход программы поступает число c (1<c<10 000).

Выходные данные
В первой строке  выведите два целых числа n и m – количество атомов и связей в разработанном нанокристалле, соответственно. Будем считать, что атомы нанокристалла пронумерованы от 1 до n. Следующие m строк должны содержать по два целых числа – пары атомов, которые следует соединить торсионными связями. Если решений несколько, выведите любое.

Если искомого нанокристалла не существует, выведите в первой и единственной строке  выходных данных два нуля.

Широкое распространение в стандартных библиотеках многих языков программирования получила реализация сбалансированных деревьев на основе так называемых красно-черных деревьев. В данной задаче вам предлагается посчитать количество красно-черных деревьев заданной формы.

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

Если вершина \(Y\) — ребенок вершины \(X\), то говорят, что вершина \(X\) является родителем вершины \(Y\). У каждой вершины дерева, кроме одной, есть ровно один родитель. Единственная вершина, не имеющая родителя, называется корнем дерева.

Соединим каждую вершину кроме корня с ее родителем. Заметим, что для каждой вершины существует ровно один путь, ведущий в нее от корня.

Двоичное дерево называется красно-черным, если каждая его вершина раскрашена в красный либо в черный цвет, причем выполняются следующие условия:

1. если вершина красная, то ее родитель — черный;

2. количество черных вершин на пути от корня до любой вершины, у которой отсутствует хотя бы один ребенок, одно и то же.

Примеры двоичного дерева, вершины которого раскрашены в два цвета, приведены на следующем рисунке.

Если считать закрашенные вершины черными, а незакрашенные — красными, то дерево на рисунке (а) является красно-черным деревом, а деревья на рисунках (б) и (в) — нет. Для дерева на рисунке (б) нарушается первое свойство — у красной вершины 5 родитель 2 также красный, а в дереве на рисунке (в) нарушается второе свойство — на пути от корня до вершины 1 одна черная вершина, а, например, на пути от корня до вершины 3 — две.

Для заданного двоичного дерева подсчитайте число способов раскрасить его вершины в черный и красный цвет так, чтобы оно стало красно-черным деревом.

Формат входных данных
Первая строка содержит число \(n\) — количество вершин в дереве (\(1 \le n \le 1000\)).

Пусть вершины дерева пронумерованы числами от \(1\) до \(n\). Следующие \(n\) строк содержат по два числа — для каждой вершины заданы номера ее левого и правого ребенка. Если один из детей отсутствует, то вместо его номера записан ноль. Гарантируется, что входные данные корректны, то есть набор чисел действительно задает двоичное дерево.

Формат выходных данных
Выведите одно число — количество способов раскрасить вершины заданного во входном файле двоичного дерева в красный и черный цвета так, чтобы оно стало красно-черным деревом.

Все допустимые способы раскрасить вершины дерева из первого примера приведены на следующем рисунке.

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

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

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

Формат входных данных
На первой строке записано целое число \(n\) — количество этапов эксперимента (\(1 \le n \le 100\)).

Следующие \(n\) строк содержат описание этапов. Пронумеруем этапы от 1 до \(n\) в некотором произвольном порядке. Тогда \(i\)-я из этих строк описывает \(i\)-й этап. Каждый этап описывается последовательностью целых чисел. Первое число равно нулю, если на этом этапе Игорь управляет генератором, и единице, если он управляет манипулятором. Затем записано целое число \(r_i\) — количество этапов, которые должны быть выполнены перед выполнением данного. За ним следуют номера этих этапов — \(r_i\) различных целых чисел в диапазоне от 1 до \(i - 1\).

Формат выходных данных
На первой строке выведите минимальное количество перемещений, которые придется совершить Игорю. На второй строке выведите перестановку чисел от 1 до \(n\) — последовательность, в которой следует выполнять этапы. Если решений несколько, выведите любое.

Всего во Флатландии \(n\) городов, пронумерованных от \(1\) до \(n\), столица Флатландии имеет номер \(1\). Компьютерная сеть Флатландии устроена следующим образом: в каждом городе есть один центр подключения, который может быть связан с некоторыми другими центрами с помощью проводных каналов связи. При этом между любыми двумя городами есть ровно один маршрут по каналам связи, иначе говоря, сеть представляет собой дерево. Для города \(i\), где \(i > 1\), обозначим первый город на маршруте от города \(i\) до столицы как \(p_i\).

Запланирована модернизация сети Флатландии, в результате которой некоторые каналы связи будут заменены на более современные оптические. Оптические каналы могут быть проложены только вместо существующих проводных. Стоимость замены канала, который соединяет город \(i\) с городом \(p_i\), равна \(w_i\). Из-за ограничений технологии любой центр подключения может быть подключен оптическими каналами не более чем к \(k\) другим центрам.

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

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

Формат входных данных
На первой строке ввода находятся два целых числа \(n\) и \(k\) (\(2 \le n \le 10^5\), \(1 \le k \le 100\)).

На следующих \(n - 1\) строках заданы описания каналов, \((i-1)\)-я из этих строк содержит два целых числа: \(p_i\) и \(w_i\) (\(1 \le p_i \le i\), \(0 \le w_i \le 10^9\)).

Формат выходных данных
Выведите два целых числа \(cnt\) и \(cost\): максимальное число каналов, которое удастся модернизировать и минимальную стоимость, за которую можно модернизировать такое число каналов.

Замечание
Конфигурация сети в первом примере до и после модернизации показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно \(4\). Стоимость модернизации любого канала равна \(0\) и не показана.

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

Конфигурация сети во втором примере до и после модернизациии показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно \(6\). Стоимость модернизации канала показана рядом с каналом, суммарная стоимость модернизации каналов в оптимальном решении равна \(27\).

На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо M-значного числа в системе счисления с основанием K (то есть, по сути, каждый участник называет M цифр, каждая из которых лежит в диапазоне от 0 до K−1). Ведущие нули в числах допускаются.

В некоторый момент прием ставок на текущий розыгрыш завершается, и после этого ведущий в телеэфире называет выигравшее число (это также M-значное число в K-ичной системе счисления). После этого те телезрители, у кого первая цифра их числа совпала с первой цифрой числа, названного ведущим, получают выигрыш в размере A₁ рублей. Те, у кого совпали первые две цифры числа — получают A₂ рублей (при этом если у игрока совпала вторая цифра, но не совпала первая, он не получает ничего). Аналогично угадавшие первые три цифры получают A₃ рублей. И так далее. Угадавшие все число полностью получают Am рублей. При этом если игрок угадал t первых цифр, то он получает A_t рублей, но не получает призы за угадывание t−1, t−2 и т.д. цифр. Если игрок не угадал первую цифру, он не получает ничего.

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

Входные данные
В первой строке задаются числа N (количество телезрителей, сделавших свои ставки, 1 ≤ N ≤ 100000), M (длина чисел 1 ≤ M ≤ 10) K (основание системы счисления 2 ≤ K ≤ 10). В следующей строке записаны M чисел A₁, A₂, ..., A_M, задающих выигрыши в случае совпадения только первой, первых двух,... , всех цифр (1 ≤ A₁ ≤ A₂ ≤ ... ≤ A_M ≤ 100000). В каждой из следующих N строк записано по одному M-значному K-ичному числу. Числа идут в порядке неубывания.

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

Примеры

№	Входные данные	Выходные данные
1	10 3 2 1 3 100 000 000 001 010 100 100 100 100 110 111	011 6
2	1 1 10 100 0	1 0

Эн идет в свой Грибной лес собирать грибы.

В Грибном лесу m ориентированных дорожек, соединяющих n деревьев. На каждой дорожке растут грибы. Когда Эн проходит по дорожке, он собирает все грибы на этой дорожке. Однако, в Грибном лесу такая плодородная почва, что грибы растут с фантастической скоростью. Новые грибы вырастают, как только Эн заканчивает собирать грибы на дорожке. А именно, после того, как Эн проходит по дорожке в i-й раз, вырастает на i грибов меньше, чем было до этого прохода. Таким образом, если на дорожке изначально было x грибов, то Эн соберет x грибов в первый проход, x - 1 гриб во второй, x - 1 - 2 гриба в третий и так далее. Однако, количество грибов не может стать меньше 0.
Например, пусть изначально на дорожке росло 9 грибов. Тогда количество грибов, которое соберет Эн, равно 9, 8, 6 и 3 для проходов с первого по четвертый. Начиная с пятого прохода и далее Эн ничего не сможет собрать с этой дорожки (но все еще может по ней ходить).

Эн решил начать от дерева s. Какое максимальное количество грибов он может собрать, передвигаясь только по описанным дорожкам?

Входные данные:
Первая строка содержит два целых числа n и m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — количество деревьев и количество ориентированных дорожек в Грибном лесу, соответственно.
Каждая из следующих m строк содержит три целых числа x, y и w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10⁸), описывающих дорожку, которая ведет от дерева x к дереву y с w грибами изначально. Возможны дорожки, которые ведут от дерева к нему же, а также несколько дорожек, соединяющих одну и ту же пару деревьев.
Последняя строка содержит одно целое число s (1 ≤ s ≤ n) — начальную позицию Эна.

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

Примеры:
 

Входные данные	Выходные данные
2 2 1 2 4 2 1 4 1	16
3 3 1 2 4 2 3 3 1 3 8 1	8

Пояснения:
В первом примере Эн может три раза пройти по кругу и собрать 4 + 4 + 3 + 3 + 1 + 1 = 16 грибов. После этого не будет грибов, которые Эн может собрать.
Во втором примере Эн может пойти к дереву 3 и собрать 8 грибов на дорожке от дерева 1 до дерева 3.

Дан граф из n вершин и m ориентированных ребер. В каждой вершине записана некоторая строчная латинская буква. 
Определим величину пути как наибольшее количество раз, которое какая-то буква встречалась на этом пути. Например, если буквы на пути образуют строку «abaca», то величина этого пути равна 3.
Ваша задача — найти путь с наибольшей величиной.

Входные данные:
Первая строка содержит два целых числа n, m (1 ≤ n, m ≤ 200000), означающих, что в графе n вершин и m ориентированных ребер.
Вторая строка содержит строку s, состоящую только из строчных латинских букв. Символ номер i — это буква, записанная в вершине номер i.
Далее следуют m строк. Каждая из этих строк содержит два целых числа x, y (1 ≤ x, y ≤ n), описывающих ориентированное ребро из x в y. Обратите внимание, x может быть равно y, и могут быть несколько ребер между x и y.
Кроме того, граф может быть несвязным.

Выходные данные:
Выведите одно число — максимальную величину пути. Если существуют пути со сколь угодно большой величиной, выведите -1.

Примеры:
 

Входные данные	Выходные данные
5 4 abaca 1 2 1 3 3 4 4 5	3
6 6 xzyabc 1 2 3 1 2 3 5 4 4 3 6 4	-1
10 14 xzyzyzyzqx 1 2 2 4 3 5 4 5 2 6 6 8 6 5 2 10 3 9 10 9 4 6 1 10 2 8 3 7	4

Дан ориентированный взвешенный ациклический граф. Требуется найти в нем кратчайший путь
из вершины s в вершину t.

Входные данные:
Первая строка входного файла содержит четыре целых числа n, m, s и t - количество вершин, ребер графа, начальная и конечная вершина соответственно (1 <= n <= 100000; 0 <= m <= 200000; 1 <= s, t <= n).
Следующие m строк содержат описания ребер по одной на строке. 
Ребро номер i описывается тремя целыми числами b_i, e_i и w_i - началом, концом и длиной ребра соответственно (1 <= b_i, e_i <= n; |w_i| <= 1000). 
Граф не содержит циклов и петель.

Выходные данные:
Первая строка выходного файла должна содержать одно целое число - длину кратчайшего пути из s в t. 
Если пути из s в t не существует, выведите "Unreachable".

Примеры:
 

Входные данные	Выходные данные
2 1 1 2 1 2 -10	-10
2 1 2 1 1 2 -10	Unreachable

Кайману снится необычный сон, будто он попал в странный район города. Этот район можно представить как граф-дерево, где вершины - это перекрестки и ребра - двусторонние дороги, которые соединяют эти перекрестки. Всего перекрестков n и у каждого свой номер от 0 до n-1.

Но не все так плохо в этом сне, ведь на каждой дороге между перекрестками с номерами u и v есть С_u,v пельменей! Кайман очень любит пельмешки, поэтому хочет съесть как можно больше, но есть проблема - если он побывает в каком-либо перекрестке более чем k раз, то на него нападет злой пельменный монстр.

Хоть это и сон, но пельмешки на каждой дороге можно съесть только один раз, хотя ничего не мешает ходить по дорогам по несколько раз. Также Кайман не останавливается на дорогах. То есть, если он начнет переходить от одного перекрестка к другому, то он обязательно пройдет дорогу полностью до следующего перекрестка.

В начале сна Кайман находится на перекрестке с номером 0. Помогите ему определить, какое максимальное количество пельменей он сможет съесть, но так, чтобы на него не напал злой пельменный монстр.

Входные данные:
В первой строке следует два целых числа n и k (3 ≤ n ≤ 10⁵; 1 ≤ k ≤ 10⁵) — количество перекрестков и максимальное количество посещений каждого из перекрестков.
В следующих n - 1 строках следует по три целых числа u, v и C_u,v (0 ≤ u, v ≤ n - 1; 0 ≤ C_u,v ≤ 10000), означающих, что перекрестки с номерами u и v связаны дорогой, на которой C_u,v пельменей.
Гарантируется, что перекрестки и дороги формируют дерево.

Выходные данные:
Выведите одно целое число - максимальное количество пельменей, которое сможет съесть Кайман.

Примеры:
 

Входные данные	Выходные данные
9 3 0 1 1 0 2 1 1 3 2 1 4 2 1 5 2 2 6 3 2 7 3 2 8 3	15
9 5 0 1 1 0 2 1 1 3 2 1 4 2 1 5 2 2 6 3 2 7 3 2 8 3	17
11 6 1 0 7932 2 1 1952 3 2 2227 4 0 9112 5 4 6067 6 0 6786 7 6 3883 8 4 7137 9 1 2796 10 5 6200	54092

Пояснение:
В первом примере нужно посетить перекрестки в следующем порядке: 0, 1, 5, 1, 3, 1, 0, 2, 6, 2, 7, 2, 8. Тогда он съест суммарно 1+2+2+1+3+3+3 = 15 пельменей.
Обратите внимание, что ни один перекресток не посещается более чем 3 раза.
 

Сегодня в замке Эна проходит фестиваль пирогов, в котором участвуют n пекарен, каждая из которых имеет свой уникальный номер от 1 до n.
Некоторые пекарни соединены между собой двусторонними дорогами, но таким образом, что если из пекарни i можно дойти до пекарни j, то существует ровно один маршрут между ними.

Когда Эн ест пироги в i-й пекарне, то он получает A_i удовольствия. А если проходит по дороге между некоторыми пекарнями с номерами v и u, то вкусный аромат пирогов приносит Эну C_v,u удовольствия.

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

Помогите Эну определить максимально возможное удовольствие, которое он сможет получить.

Входные данные:
В первой строке дано число n (1 <= n <= 50000) - количество пекарен, и число k - количество существующих дорог между пекарнями.
Во второй строке дано n чисел A_i (0 <= A_i <= 10000) - удовольствие от пирогов i-й пекарне.
Далее следует k строк, в каждой по 3 числа v, u, C (1 <= v, u <= n; v ≠ u; 0 <= C <= 10000), означающие, что существует дорога между пекарнями с номерами v и u, и аромат на этой дороге приносит C удовольствия.

Выходные данные:
Выведите одно число - максимально возможное удовльствие.

Примеры:
 

Входные данные	Выходные данные
2 1 1 1 1 2 1	3
8 7 1 5 4 6 10 1 2 2 1 2 1 2 3 10 2 4 1 4 5 1 4 6 2 6 7 2 6 8 3	37

Пояснения:
В первом примере нужно начать в 1-й пекарне (1 удовольствие), пройти по дороге между 1-й и 2-й пекарнями (1 удовольствие) и посетить 2-ю пекарню (1 удовольствие). Суммарное удовольствие - 1+1+1 = 3.
Во втором примере нужно начать в 5-й пекарне (10 удовольствия), пройти по дороге между 5-й и 4-й пекарнями (1 удовольствие), посетить 4-ю пекарню (6 удовольствия), пройти по дороге между 4-й и 2-й пекарнями (1 удовольствие), посетить 2-ю пекарню (5 удовольствия), пройти по дороге между 2-й и 3-й пекарнями (10 удовольствия), посетить 3-ю пекарню (4 удовольствия). Суммарное удовольствие - 10+1+6+1+5+10+4 = 37.

Вам дано дерево (связный ациклический неориентированный граф), состоящее из n вершин.
Найдите размер его максимального паросочетания (набор попарно несмежных ребер).

Входные данные:
В первой строке дано число n - количество вершин в дереве.
Далее идет n-1 строка, в каждой из которых дается по два числа a_i и b_i (1 <= a_i, b_i <= n) - ребра дерева.

Выходные данные:
Выведите одно число - размер максимального паросочетания данного дерева.

Примеры:
 

Входные данные	Выходные данные
4 1 2 2 3 3 4	2

Пояснение:
В максимальное паросочетание данного дерева будут входить ребра 1-2 и 3-4.

Мирко стал генеральным директором крупной корпорации. В компании работает N человек, которые пронумерованы числами от 1 до N, причем сам Мирко имеет номер 1. У всех работников, кроме Мирко, есть начальник. Начальник может иметь несколько подчиненных, но не более одного своего начальника.

Когда Мирко получает задание от инвесторов, он передает его своему подчиненному с наименьшим номером. Этот подчиненный также передает его своему подчиненному с наименьшим номером, и так далее, пока задание не перейдет несчастливому работнику без подчиненных, который должен его выполнить.
Этот работник получает 1 монету, его начальник получает 2 монеты, начальник этого начальника получает 3 монеты, и так далее. Потом тот, кто на самом деле сделал работу, осознает, насколько эта капиталистическая система несправедлива, и увольняется с работы.

Мирко получает задания до тех пор, пока в корпорации не останется всего один сотрудник — сам Мирко. Тогда он выполняет это задание, получает 1 монету и уходит из корпорации.

Ему стало интересно, сколько всего монет получил каждый бывший сотрудник. Помогите ему с этим.

Входные данные:
Первая строка содержит одно натуральное число N (1 ≤ N ≤ 2·10⁵) — число сотрудников компании. Следующая строка содержит N-1 чисел a₂, a₃, ... a_n (1 ≤ a_i < i), a_i — номер начальника i-го сотрудника.

Выходные данные:
Выведите N чисел, i-е число должно означать, сколько монет получил i-й сотрудник.

Примеры:
 

Входные Данные	Выходные данные
3 1 1	5 1 1
5 1 2 2 4	13 8 1 3 1

Пояснения:

Далее приведено описание ко второму примеру.

Мирко отдает первое задание работнику 2, который передает его работнику 3, который выполняет задание. Таким образом, работник 3 получает одну монету, работник 2 — две монеты, а работник 1, сам Мирко, — три монеты. После этого работник 3 увольняется.
Мирко отдает второе задание работнику 2, который передает его работнику 4, который тут же передает задание работнику 5, который выполняет задание. После этого работник 5 получает одну монету, работник 4 — две монеты, работник 2 — три монеты, а Мирко — четыре монеты. Работник 5 увольняется.
После выполнения третьего задания работник 4 получает одну монету, работник 2 — две монеты, а Мирко — три монеты, после чего работник 4 увольняется.
После выполнения четвертого задания работник 2 получает одну монету, а Мирко — две монеты, после чего второй работник увольняется.
Наконец, пятое задание выполняет сам Мирко, получая за это одну монету, после чего процесс прекращается.

Суммарно Мирко получил 13 монет, работник 2 — 8 монет, работник 4 — 3 монеты, а работники 3 и 5 — одну монету.

В тридесятом государстве есть N деревень. Некоторые пары деревень соединены дорогами. В целях экономии, “лишних” дорог нет, т.е. из любой деревни в любую можно добраться по дорогам единственным образом.
Новейшие исследования показали, что тридесятое государство находится в сейсмически опасной зоне. Поэтому глава государства захотел узнать, какой именно ущерб может принести его державе землетрясение. А именно, он хочет узнать, какое минимальное число дорог должно быть разрушено, чтобы образовалась изолированная от остальных группа ровно из P деревень такая, что из любой деревни из этой группы до любой другой деревни из этой группы по-прежнему можно будет добраться по неразрушенным дорогам (группа изолирована от остальных, если никакая неразрушенная дорога не соединяет деревню из этой группы с деревней не из этой группы).
Вы должны написать программу, помогающую ему в этом.

Формат входных данных
Первая строка входного файла содержит два числа: N и P (1 ≤ P ≤ N ≤ 150). Все остальные строки содержат описания дорог, по одному на строке: описание дороги состоит из двух номеров деревень (от 1 до N), которые эта дорога соединяет. Все числа во входном файле разделены пробелами и/или переводами строки.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 2 1 2 3 2	1
2	11 6 1 2 1 3 1 4 1 5 2 6 2 7 2 8 4 9 4 10 4 11	2	группа деревень (1, 2, 3, 6, 7, 8) окажется изолированной от остальных, если разрушить дороги 1–4 и 1–5.

Гурман Яблочков работает редактором известного гастрономического издания. Он разъезжает по всему миру, дегустируя новые изыски именитых шеф-поваров самых фешенебельных ресторанов высокой кухни. У Яблочкова есть свой фирменный способ ревью: в каждом заведении Яблочков заказывает два набора блюд в разные дни. Все заказанные блюда разные, так как Яблочков не любит есть одно и то же. Для каждой пары блюд из разных наборов он точно помнит, какое из них лучше по его ощущениям, или что они одинаковы по вкусовым качествам. Затем гурман оценивает каждое блюдо положительным целым числом.

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

Гурман в первый день дегустировал набор из n блюд, во второй день набор из m блюд. Он составил таблицу ощущений a размером nm, в которой описал свои впечатления. Если по мнению эксперта блюдо i из первого набора лучше блюда j из второго набора, то a_ij равно « > », в противоположном случае a_ij равно « < ». Блюда также могут быть равны по уровню, тогда a_ij равно « = ».

Теперь Яблочков хочет, чтобы вы помогли ему оценить каждое блюдо в наборах целым положительным числом. Так как Яблочков очень строгий дегустатор, то постарается оценить блюда так, чтобы максимальная из оценок была как можно меньше. В то же время Яблочков очень справедливый, поэтому никогда не оценивает блюда так, чтобы это шло вразрез с его ощущениями. Другими словами, если a_ij равно « < », то оценка блюда i из первого набора должна быть меньше оценки блюда j из второго набора, если a_ij равно « > », то должна быть больше, а если a_ij равно « = », то должна совпадать.

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

Входные данные
В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 1000 ) — количества блюд в каждый из двух дней.

Каждая из следующих n строк содержит строку из m символов. j-й символ в i-й строке задаёт значение aij. Все строки состоят только из символов « < », « > » и « = ».

Выходные данные
В первой строке выведите « Yes » (без кавычек), если можно сделать корректную оценку всем блюдам и « No » (без кавычек), если иначе.

В случае, если сделать корректную оценку можно, во второй строке выведите n целых чисел — оценки блюд первого набора, а в третьей строке m целых чисел — оценки блюд второго набора.
 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 4 >>>> >>>> >>>>	Yes 2 2 2  1 1 1 1	Все блюда первого дня лучше всех блюд второго дня. Значит, самой высокой оценкой будет 2 для всех блюд первого дня.
2	3 3 >>> <<< >>>	Yes 3 1 3  2 2 2
3	3 2 == =< ==	No	Таблица противоречива: нет ни одного набора оценок, который удовлетворял бы ей.