[CodeForces - 1084D] The Fair Nut and the Best Path(트리 dp)
3604 단어 동적 계획 (dp)Codeforce~
The Fair Nut is going to travel to the Tree Country, in which there are nn cities. Most of the land of this country is covered by forest. Furthermore, the local road system forms a tree (connected graph without cycles). Nut wants to rent a car in the city uu and go by a simple path to city vv. He hasn't determined the path, so it's time to do it. Note that chosen path can consist of only one vertex.
A filling station is located in every city. Because of strange law, Nut can buy only wiwi liters of gasoline in the ii-th city. We can assume, that he has infinite money. Each road has a length, and as soon as Nut drives through this road, the amount of gasoline decreases by length. Of course, Nut can't choose a path, which consists of roads, where he runs out of gasoline. He can buy gasoline in every visited city, even in the first and the last.
He also wants to find the maximum amount of gasoline that he can have at the end of the path. Help him: count it.
Input
The first line contains a single integer nn (1≤n≤3⋅1051≤n≤3⋅105) — the number of cities.
The second line contains nn integers w1,w2,…,wnw1,w2,…,wn (0≤wi≤1090≤wi≤109) — the maximum amounts of liters of gasoline that Nut can buy in cities.
Each of the next n−1n−1 lines describes road and contains three integers uu, vv, cc (1≤u,v≤n1≤u,v≤n, 1≤c≤1091≤c≤109, u≠vu≠v), where uu and vv — cities that are connected by this road and cc — its length.
It is guaranteed that graph of road connectivity is a tree.
Output
Print one number — the maximum amount of gasoline that he can have at the end of the path.
Examples
Input
3
1 3 3
1 2 2
1 3 2
Output
3
Input
5
6 3 2 5 0
1 2 10
2 3 3
2 4 1
1 5 1
Output
7
Note
The optimal way in the first example is 2→1→32→1→3.
The optimal way in the second example is 2→42→4.
제목 대의:
모든 점에는 권한이 있고, 모든 변에도 권한이 있습니다. 경로에 있는 점의 권한과 경계권과 최대치를 줄일 수 있는 경로를 선택할 수 있습니다. 답은 단지 하나의 점으로 이 최대치를 출력할 수 있습니다.
문제 해결 보고서:
나무형 dp는 각 점을 두루 돌아다닐 때 최대치와 차대치를 유지하고 그 최대치를 되돌려준다. 그리고 답은 그 자체, 그와 그의 나무 한 그루, 그와 그의 나무 두 그루에서 각각 옮길 수 있다.(문제에서 권한이 정수일 수 있으므로 tmp1과 tmp2에 0을 직접 부여할 수 있습니다. 그러면 maxxx를 세 번 업데이트하지 않아도 됩니다.)
AC 코드:
#include
#include
#include
#include
#include
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
동적 기획 문제 풀이의 일반적인 사고방식동규로 돌아가는 일반적인 전환 방법 귀속 함수에는 n개의 매개 변수가 있는데 하나의 n차원의 수조를 정의한다. 수조의 다음 표는 귀속 함수 매개 변수의 수치 범위이고 수조 원소의 값은 귀속 함수의 귀환 값이다. 이렇...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.