I really liked the problem and after a bit thinking I think I found a solution with centroid decomposition. The main idea is that each time after we pick a new centroid with dynamic programming we look at the number of beautiful subsets with our centroid included in them.

First idea which comes to our mind is to root the current subgraph at the centroid and then do dynamic programming with state dp[u][k'] = number of subsets with root u and sum of values k'. The most basic way is to make for every state O(K) transitions so overall complexity of the dp will be O(NK²). And then complexity of the solution will be .

By the way this dp is actually a valid solution to the problem. We can simply pick an arbitrary vertex of our tree as a root and do the dp. Then the answer will be . And the complexity will be O(NK²).

Lets go back to our centroid decomposition solution. To make it more efficient. We will change the dynamic programming to dp[i][k'] = number of subsets on the first i vertices with root equal to our centroid with sum of values k'. By "first i" I mean first i in dfs order. It's not hard to do this in O(NK) time. So in such a way we create an solution.