Trim A Tree

Problem Statement

Trim A Tree Problem A farmer owns a tree with N nodes, numbered from 1 to N . A tree is an undirected connected graph with N vertices and N - 1 edges, with no self-loops and no multiple edges. The edges are given by two arrays U and V : for every i , there is an edge between node U[i] and node V[i] . In one operation the farmer chooses any edge that is still present and deletes it. Deleting an edge splits the current tree into exactly two connected components, both of which are trees. The farmer keeps one of them and discards the other. He may apply this operation any number of times, including zero times. The farmer also has an array A of size N . A node whose degree in the final tree is d contributes A[d] to the score. The total score of the final tree is the sum of these contributions over all of its nodes. Print the maximum total score the farmer can be left with. Input Format The first line contains an integer N , the number of nodes and the size of A . The second line contains an