All Tracks Algorithms Dynamic Programming Problem

Happiness Tour
Tag(s):

Algorithms, DFS, Dynamic Programming, Kadane, Medium, Trees

Problem
Editorial
Analytics

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.

SAMPLE INPUT
2
3
-1 1 2
2
1 1
2 3
8
-1 -3 4 2 1 5 -3 -3
7
1 1 2 3 3 5 6
2 3 4 5 6 7 8
SAMPLE OUTPUT
2
9
Explanation

First testcase :
Mike will skip City 1 and travel to City 2 which increases Mike's happiness to 2.

Second testcase :
Mike will skip City 1 and travel to City 3, which increases Mike's happiness to 4 and then he travels to City 6, which increases Mike's happiness to 9.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 255 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Capillary Technologies

Challenge Name

Capillary Software Developer Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?