Maximum Sum in a Binary Tree with Exclusions

Given a binary tree with n nodes where each node holds an integer value, your task is to select a subset of nodes such that no two chosen nodes are either in a direct parent-child relationship or are siblings. The goal is to maximize the total sum of the selected node values.

The tree is provided in level-order format, and the connections between the nodes (edges) are given as pairs of integers; node indices start at 1.

Formally, if you select nodes with indices in set S, then for every pair of nodes i, j in S, neither (i, j) should be an edge representing a parent-child relationship nor should they be connected as siblings. You are required to compute the maximum possible sum of the values of the nodes in S.

The solution may employ dynamic programming using a depth-first search (DFS) strategy to consider whether to include or exclude each node.

inputFormat

The first line contains an integer n representing the number of nodes. The second line contains n space-separated integers representing the values of the nodes in level order. The following n-1 lines each contain two space-separated integers u and v denoting an edge between nodes u and v.

outputFormat

Output a single integer: the maximum sum of node values such that no two selected nodes are in a disallowed (parent-child or sibling) relationship.## sample

5
10 1 2 3 4
1 2
1 3
2 4
2 5

17