You are given a tree and a constant K. The nodes of the tree are numbered from 1 to N. Each node in the tree has a value associated with it, A[i], where A[i] is either 1 or 0.
A tree is considered beautiful if the sum of its node values is equal to the given constant, K.
Georg wants to make the tree beautiful by removing any number of nodes (and their edges) from the tree, such that the tree still remains connected.
Your task is to count the number of ways to make the tree beautiful and print it modulo 10^9 + 7. Input format: Two integers N and K on the first line followed by the values of the N nodes in the next line. Lines 3 to (N + 1) contain the edges, where each pair of numbers indicates an undirected edge between those nodes.
Sample Input:
5 2
0 1 0 1 1
1 2
1 3
1 4
2 5
Output: 5
Constraints: N <= 1e5, K <= 100
Please help me with this problem. It feels like a DP on trees problem, but I’m unable to find the recurrence.
Have you tried dp[i][j] = number of ways to build subtree at node i with exactly j 1-nodes where total answer is dp[root][k]?
Could you walk me through the state transitions? ( sorry, but I've just started with this topic and I'm not very comfortable with it yet )
Auto comment: topic has been updated by Doritos4 (previous revision, new revision, compare).
Can you provide link to the question?
https://www.codechef.com/problems/ANATREE/
Please
it is knap sack dp