Maximum sum path - MarisaOJ: Marisa Online Judge

Maximum sum path

Time limit: 1000 ms
Memory limit: 256 MB
Given a tree of $n$ vertices, vertex $i$ has the number $A_i$ on it. Find a simple path with maximum sum. ### Input - The first line contains an integer $n$. - The second line contains $n$ integers $A_i$. - The next $n - 1$ lines, each line contains 2 integers $u, v$, there is an edge between $u$ and $v$. ### Output - Print the maximum sum. ### Constraints - $1 \le n \le 10^5$. - $0 \le |A_i| \le 10^9$. ### Example Input: ``` 5 1 -2 3 4 -5 1 2 2 3 3 4 4 5 ``` Output: ``` 7 ```