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

Дан граф из 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 пекарен, каждая из которых имеет свой уникальный номер от 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.