You are given a rooted tree with () nodes. The nodes are numbered from to , and the root of the tree is labelled .
Each vertex has a weight attached, namely () for the vertex labelled .
Write a program to find the maximal weight sum that can be achieved by selecting a subset of nodes from the tree, with the added restriction that a node and its parent cannot be simultaneously selected.
The first line contains the number of vertices .
The next line contains integers containing weights .
For the next lines are two integers where . This represents an edge from vertex and vertex .