DP on trees problem

Revision en4, by Doritos4, 2018-10-04 21:31:50

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Doritos4 2018-10-04 21:31:50 4 Tiny change: 'is either 0 or 1.\n\nA tre' -> 'is either 1 or 0.\n\nA tre'
en3 English Doritos4 2018-10-04 21:30:50 2 Tiny change: 'put: 5\n\nConstr' -> 'put: 5\n\n\nConstr'
en2 English Doritos4 2018-10-04 15:04:10 2 Tiny change: 'e nodes.\nSample I' -> 'e nodes.\n\nSample I'
en1 English Doritos4 2018-10-04 12:45:47 1011 Initial revision (published)