Happiness Tour
Practice
5 (1 votes)
Dynamic programming
Tree
Medium
Algorithms
Kadane
Depth First search
Problem
73% Success 1251 Attempts 30 Points 1s Time Limit 255MB Memory 1024 KB Max Code

In Wonderland, there are N cities (enumerated from 1 to N) connected by \(N-1\) bidirectional roads. Every city has an associated happiness score \(H[i]\) related to it.
Mike starts from the capital city, \(City \; 1\), and can only travel from \(City \; U\) to \(City \; V\), if the two cities are directly connected through a road. The happiness of the city, \(H[i]\), is added to Mike's own happiness when he travels through the city. He can skip any number of cities while traveling, but that would reset his happiness to 0 (that is, when Mike skips some city, his happiness is set back to 0). Once visited or skipped, he would not be able to visit or skip that city again. Mike wants to find the maximum happiness that can be achieved during his tour. Initially, Mike's happiness is zero.
Your task is to calculate the maximum happiness that Mike can achieve during his tour.

Input Format

The first line contains an integer T, denoting the number of test cases.
For each testcase :
The first line contains an integer N, denoting the number of cities.
The second line contains N space-separated integers, the i-th of which is \(H[i]\), denoting city \(i\) has happiness score \(H[i]\).
The third line contains M, the number of roads.
The fourth and fifth lines contain \(N-1\) space-separated integers, the \(i^{th}\) of which is \(U[i]\) and \(V[i]\) respectively. They denote that there is a bidirectional road between \(City \; U\) and \(City \; V\).

Input Constraints

\(1 \le T \le 10 \)
\(1 \le N \le 10^{5} \)
\(-10^{9} \le H[i] \le 10^{9}\)
\(1 \le U , V \le N\)
\(M = N-1\)
It is guaranteed that any city can be reached from any other city.

Output Format

For each test case, print the maximum amount of happiness that Mike can achieve.
Answer for each test case should come in a new line.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
10 votes
Tags:
Dynamic ProgrammingAlgorithmsTrees
Points:30
2 votes
Tags:
Dynamic programmingAlgorithmsMediumTreesDynamic Programming
Points:30
Tags:
Medium