Динамическое программирование на поддеревьях

Вы играете в игру «Бинарная Сила» и управляете персонажем, у которого есть 𝑑 = 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\), столица Флатландии имеет номер \(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\).

Кайману снится необычный сон, будто он попал в странный район города. Этот район можно представить как граф-дерево, где вершины - это перекрестки и ребра - двусторонние дороги, которые соединяют эти перекрестки. Всего перекрестков 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 — одну монету.