2517. Choose Edges to Maximize Score in a Tree

Medium
Dynamic Programming
Tree
Depth-First Search

Description

Hints

Hint 1
Use dynamic programming to recursively solve the problem for smaller subtrees.
Hint 2
You can ignore the edges with negative weights.
Hint 3
The states of the dp are the following: the root of the subtree you are at, and a boolean variable that will tell you if you have chosen the edge that connects that node and its parent.
Hint 4
What are the transitions of this dp?

Statistics

Acceptance
56.5%
Submissions
3,634
Accepted
2,054