This blog discusses potential solutions to this problem.

It's a famous technique and all you can find online is this comment on a blog discussing the problem.

I tried hard to understand it by drawing a tree and following up with how it works, but it seemed a bit confusing to me (probably a skill issue), and this idea was all the resources I found online on the trick.

Also, what about if there are variants (e.g. maximum sum of values with weight exactly $$$W$$$ instead of at most)?

There comes a brilliant idea by my friend IsaacMoris. It goes as follows:

1. Do classical Euler tour indexing (or tree flattening) to obtain three arrays $$$\text{tin}$$$, $$$\text{tout}$$$, $$$\text{vertex}$$$, where $$$\text{vertex}$$$ is defined as $$$\text{vertex}[\text{tin}[i]] = i$$$ for all $$$0 \le i \lt n$$$, and so the subtree of the vertex $$$v$$$ is the subarray $$$[l, r]$$$ in $$$\text{vertex}$$$ where $$$l = \text{tin}[v]$$$ and $$$r = \text{tout}[v] - 1$$$.

2. Do take or leave DP on the $$$\text{vertex}$$$ array as follows: either

• take the current item and go to the next element in the vertex array (corresponding to a vertex in the subtree of the current node), so dp[i][j] = dp[i + 1][j - weight[vertex[i]] + value[vertex[i]], or

• leave the current item and so skip the entire subtree. In other words, do the transition dp[i][j] = max(dp[i][j], dp[tout[vertex[i]]][j])

That's really it. This is my accepted submission based on this idea!