Problem Statement

Problem Statement A company has N employees numbered from 1 to N . Employee 1 sits at the top as CEO, and every other employee reports to exactly one direct manager, so the whole company forms a tree (the corporate hierarchy). Employee i carries a productivity value P[i] , which may be positive (a strong performer), negative (a problem employee), or zero. Management wants to hand-pick a group of employees for a special project, with one restriction: an employee and their direct manager can never both be chosen, since the project depends on each participant deciding independently. Work out the largest possible sum of productivity values over any valid group of employees. Input Format First line contains a single integer N . Second line contains N space-separated integers representing productivity values P[1], P[2], ..., P[N] . Next N-1 lines each contain two integers u and v representing that u is the direct manager of v . Output Format Print a single integer - the maximum sum of produc