Задача №113730. Соляной рудник
Влад приехал на экскурсию на соляной рудник, состоящий из n соляных пещер. Как Влад узнал от экскурсовода, эти пещеры соединены n - 1 туннелями, пронумерованными от 1 до n - 1 . Кроме того, известно, что можно дойти от любой пещеры до любой другой пещеры, используя только данные туннели. Изучив карту рудника, Влад оценил для каждого туннеля его красоту . Для того, чтобы насладиться красотой природных объектов, необходимо смотреть на них с нужного ракурса. Поэтому красота туннеля зависит от того, в какую сторону идти по нему.
Для каждого туннеля i , соединяющего пещеры с номерами u i и v i , Влад определил два числа p i и q i — красоту туннеля, если пройти его от u i до v i и красоту туннеля, если пройти его от v i до u i соответственно. Красоты задаются целыми числами и могут быть отрицательными в случае, если соответствующий туннель показался Владу некрасивым.
Сейчас Влад находится в пещере с номером 1 и хочет дойти до пещеры с номером n , максимизировав сумму красот туннелей, которые он посмотрит за время своего путешествия. Однако Влад всё же боится заблудиться, поэтому вдоль каждого туннеля он хочет пройти не более, чем один раз в каждую сторону. Помогите Владу определить наиболее красивый маршрут.
В первой строке задано целое число n ( 1 ≤ n ≤ 100 000 ) — количество пещер в руднике.
В следующих n - 1 строках задано описание туннелей. Каждое описание состоит из четвёрки чисел u i , v i , p i , q i ( 1 ≤ u i , v i ≤ n , u i ≠ v i , - 10 4 ≤ p i , q i ≤ 10 4 ) — номеров пещер, которые соединяет i -й туннель и значений его красоты при движении от u i к v i и при движении от v i к u i соответственно.
Выведите одно целое число — максимально возможную красоту маршрута от пещеры с номером 1 до пещеры с номером n .
В первом тестовом примере Владу выгодно пойти из пещеры 1 в пещеру 2 , а затем — из пещеры 2 в пещеру 3 . В таком случае суммарная красота маршрута составит 5 + 1 = 6 .
Во втором тестовом примере Владу выгодно пройти из пещеры 1 в пещеру 4 , затем вернуться в пещеру 1 , а затем дойти до пещеры 5 через пещеру 2 . Суммарная красота в таком случае равна 2 + ( - 1) + 1 + 1 = 3 .
В третьем тестовом примере Владу выгодно дойти из пещеры 1 в пещеру 4 , затем из пещеры 4 в пещеру 2 и вернуться в пещеру 4 . Красота в таком случае равна 1 + 7 + ( - 6) = 2 .
3 1 2 5 2 2 3 1 3
6
5 1 2 1 1 2 5 1 1 1 4 2 -1 2 3 1 -2
3
4 1 4 1 1 2 3 -10 2 4 2 7 -6
2