Money Thief

0

0 votes
Problem

The burglar has found himself a new place for his Thievery again. They can only enter this area through a special house called "root". Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place forms a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Input:
A line containing an integer T, the no. of Test Cases.
First Line of each test case contain an integer N, the no. of Nodes in the tree.
Next line containing N integers, the values on the nodes.where '-1' indicates a NULL node.


Output:
Output for each Test Case the maximum amount of money the thief can rob tonight modulo 10^9+7 in one Line.

Constraints:
1<= T <= 100
1<= N <= 5000
1<= A[i] <=10^9

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In 1st test case:
      3*
    /   \
   2     3
   \      \
    3*     1*


Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

 

 

In 2nd test case:


      3
    /   \
   4*    5*
  / \      \ 
 1   3      1 

 Maximum amount of money the thief can rob = 4 + 5 = 9.

Editor Image

?