### druh's blog

By druh, history, 12 months ago, ,

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.

• 0

 » 12 months ago, # |   +1 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]?
•  » » 12 months ago, # ^ |   0 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 )
 » 12 months ago, # |   0 Auto comment: topic has been updated by druh (previous revision, new revision, compare).
 » 12 months ago, # |   0 Can you provide link to the question?
•  » » 12 months ago, # ^ |   0
 » 12 months ago, # |   0 Please