smoothie-web Problems Contests Ranking About
Login Register

BSSPC 2019 P10 - Tree Subsets

data_usage Points
timer Time Limit
linear_scale Memory Limit

Problem Statement

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

Each vertex has a weight attached, namely viv_i (105vi105-10^5\leq v_i\leq 10^5) for the vertex labelled ii.

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 NN.

The next line contains NN integers containing weights v1,,vnv_1,\ldots,v_n.

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