### The Problem

You are planning a corporate party. Every employee e has an amount f(e) \geqslant 0 of fun that they will bring to the party if invited. The total fun in the party is the sum of f(e) over all invited employees e. You want your party to be very fun. In fact, as fun as possible. However, it turns out that if you invite a manager and their direct report together, the party will be absolutely no fun, not for anyone. What’s the best you can do?

Concretely, the problem is the following.

- We are given a graph G = (V,E) that is a rooted tree on n vertices with a weight function w: V \longrightarrow \mathbb{N} and root r.
- We want to output the weight of a max-weight independent set in G.

### The Solution

For v \in V, let T[v] denote the weight of a max-weight independent set in G_v, which is the subtree of G rooted at v.

Indeed, T[r] is what we want!

If v is a leaf node, then T[v] = w(v).

For the sake of analysis, fix a max-weight independent set S of G_v. We have to wonder: does S contain v?

- If the answer is no, then S can be viewed as a union of optimal solutions in all the subtrees rooted at the chindren of v.
- If the answer is yes, then S can be viewed as a union of optimal solutions in all the subtrees rooted at the grandchindren of v (since the children are now forbidden), and the vertex v itself.

As always, we take the best of both worlds when we pen down our recurrence:

\operatorname{T}(v)=\max \left\{\sum_{w \downarrow v} \operatorname{T}(w), 1+\sum_{w \downarrow v} \sum_{x \downarrow w} \operatorname{T}(x)\right\},

where the notation w \downarrow v means “w is a child of v”.

Proceed from the leaves of the tree upwards.