BSSPC 2019 P10 - Tree Subsets

Problem Statement

You are given a rooted tree with $N$ ($1\leq N\leq 10^5$) nodes. The nodes are numbered from $1$ to $N$, and the root of the tree is labelled $1$.

Each vertex has a weight attached, namely $v_i$ ($-10^5\leq v_i\leq 10^5$) for the vertex labelled $i$.

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.

Input Specification

The first line contains the number of vertices $N$.

The next line contains $N$ integers containing weights $v_1,\ldots,v_n$.

For the next $(N-1)$ lines are two integers $i,j$ where $1\leq i,j\leq N$. This represents an edge from vertex $i$ and vertex $j$.