Doritos4's blog

DP on trees problem

By Doritos4, history, 6 years 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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years 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]?

→ Reply
  • »
    »
    6 years 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 )

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide link to the question?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

it is knap sack dp

→ Reply