Compute sum of edges in paths from source to target node? Given a directed acyclic graph G = (V,E). Suppose that the vertices are in topological sort, in particular there exist an edge $(u,v) \in E$ if u &lt;v (see the graph below). The weight $w(u,v)$ on each edge is a positive number. For a given node $i$, I am interested in computing the  following term $s[i]$ defined as follows:
s[i] is sum of weights on any edges (w.o duplicates) of some paths from the source node 1 to the node i.
For example, in the below graph s[6] =  3+ 2+ 10 + 20 + 200 + 100 = 335.
I am struggling how to come up with a linear time w.r.t $|V|$ and $|E|$ to compute $s[i]$ for a given node $i$.
I am thinking of using dynamic programing. For example, suppose we already can compute $s[j]$ up to $j&lt;k$, to compute $s[k]$ we might attempt $s[k] = \sum_{i} s[i] + w[i,k]$ if there is an edge $(i,k)$. For example, to compute $s[6]$ we need $s[4]$ and $s[5]$,
So $s[6] = (s[4] + 200) + ( s[5]+ 100) = (3+200) + ( (3+2+20+2+10) +100) $ but this approach fails since we did not take into account that  the edge $(1,4)$ is shared in computing $s[4]$ and $s[5]$. The edge $(1,4)$ should be summed one time in $s[6]$.
A simple approach that should work w/out need for a hash table is as follows:
Let two boolean arrays $a,b$ such that

$a[u] =1 $ iff a path $1 \ldots u$ exists

$b[u] =1$ if a path $u  \ldots i$ exists


Both can be calculated in $O(V+E)$ time : $a$ with a simple BFS from $1$, and $b$ by a bottom-up approach of examining the vertices in the reverse topological order.
Now, you consider each edge of the graph $ u \rightarrow v$ and add $w(u,v)$  to the answer iff $a[u]=1$ and $b[v]=1$.
Because the graph is a DAG the two paths above must be disjoint thus their concatenation is a valid path from $1$ to $i$ and since we consider each edge once, there are no duplicates.