Counting in a DAG

[zobayer]

The problem is DAGCNT2 from SPOJ [ https://www.spoj.pl/problems/DAGCNT2 ]

Please anyone give me some hint about the proper algorithm to solve it. I used dfs with some optimization, but actually, I have gone upto n^2 somehow.

Thanks in advance!

[aab]

Sort the vertices in topological order.You can do it in O(n+m) with dfs. Then for each vertex (starting from vertex of lower priority) calculate the sum of the weights of the vertices within its reach. This is also done in O(n+m). This should work.