A was thinking about a DAG problem. It goes as follows:

You are given a directed acyclic graph with N nodes and M edges. Every vertex has a number associated with it, let us call it A[i]. The power of every vertex is defined as the sum of values written on every vertex reachable from it. We are given Q queries. In each query we need to find the power of a given vertex.

For example, Let N = 5, M = 5 and the value of A = {2, 3, 1, 4, 2}. (Assume 1-based indexing). Let the edges be {(2, 1), (3, 1), (4, 2), (4, 3), (3, 5)}, where (x, y) means there is directed edge from x to y.

So, querying for vertex 4, gives a answer of (2 + 3 + 1 + 4 + 2) = 12, as every vertex is reachable from it, while for vertex 3, it gives answer as (2 + 3 + 2) = 7 as only {1, 3, 5} are reachable from it.

The brute force solution is to perform dfs/bfs in every query. If possible, can you please provide an efficient algorithm for this. (I was thinking about some kind of precomputation using topological sort, but ended but added some values more than once.)

Thank you.