You are given a tree T with n vertices, rooted at vertex 1. Each vertex i has an associated value ai , which may be nega

[answerhappygod]

You are given a tree T with n vertices, rooted at vertex 1. Each
vertex i has an associated value ai , which may be
negative.
You wish to colour each vertex either red or black. However, you
must ensure that for each pair of red vertices, the path between
them in T consists only of red vertices.
Design an algorithm which runs in O(n) time and
finds the maximum possible sum of values of red vertices,
satisfying the constraint above.
Clarifications:
• Are there any constraints on the values ai? No. In
particular, they may be negative.
• Is T a binary tree? Not necessarily.
• Is it valid to colour all vertices in black? The problem
statement suggests that the answer should be yes, but if you
instead take the interpretation that the answer is no (i.e. at
least one vertex must be coloured in red), you will not be
penalised.
Hint: Try to solve the problem within subtrees, with subproblems
indexed by the root of each subtree.
Do not write the code, give steps and
methods.
Explain the steps of algorithm, and the logic behind
these steps in plain English and give Diagrams and time
complexity