Lesson 5

To solve the weighted problem, the greedy algorithm will no longer work: if we immediately take a leaf into the solution, then we will definitely not take its neighbor (or parent), but this neighbor may have a large weight.

We will use the method of dynamic programming, and here it will be a bit more convenient to assume that the tree is rooted. We will move up the tree and calculate the index of happiness \(F(v)\) of each subtree with root at vertex \(v\) using the recurrence formula: \[F(v)=\max\left\lbrace w(v)+ \sum\limits_{\substack{\text{grandchildren $w$ } \\ \text{of vertex $v$}}}F(w), \sum\limits_{\substack{\text{children $w$ } \\ \text{of vertex $v$}}}F(w) \right\rbrace \ .\] The result is shown in the figure below.