Help in a dp on trees problem

Revision en2, by Black_hat123, 2019-07-23 12:14:35

Hello, Can anyone please tell how to solve below problem — There exists a special graph which has directed M edges and N nodes and graph contains no cycles. Count the number of ways to reach different nodes from S. A way is called different from others if the destination node or used edges differ. As the ways can be large, print the ways modulo 1000000007. Include source node as destination also. 1 <= S, N <= 100005 (S=source vertex) (N=number of nodes) 1 <= M <= 200005 (number of edges) 1 <= x , y <= N (edge from x to y)

My approach is to use dp on tree 1)Make a reverse graph (all edges are in reverse order) 2)call DP recursive function for all nodes who are not yet visited 3)Inside Dp recursive function call for number of ways to reach to parent of current node from Source(S)(Using the reverse graph) and add all those ways to dp[current_node] 4)return dp[current node] But this approach is giving TLE in some testcases. Please suggest some ideas... Problem link

Thanks :)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Black_hat123 2019-07-23 12:14:35 25 Tiny change: ' Source(S) and add ' -> ' Source(S)(Using the reverse graph) and add '
en1 English Black_hat123 2019-07-23 12:12:46 1080 Initial revision (published)