druh's blog

By druh, history, 6 weeks ago, In English,

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.

 
 
 
 

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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]?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 )

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by druh (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide link to the question?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please