DP on trees problem 
Difference between en3 and en4, changed 4 character(s)
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 01 or 10.↵
↵
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 <br>↵
0 1 0 1 1 <br>↵
1 2 <br>↵
1 3 <br>↵
1 4 <br>↵
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)