In a directed acyclic graph with a source vertex $\mathbf{s}$, the *quality-score* of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex $v$ other than $\mathbf{s}$, the quality-score of $v$ is defined to be the maximum among the quality-scores of all the paths from $\mathbf{s}$ to $v$. The quality-score of $\mathbf{s}$ is assumed to be 1. The sum of the quality-scores of all the vertices in the graph shown above is ________.

Let $Q(v)$ denote the quality-score of vertex $v$. Since the graph is a directed acyclic graph (DAG), we can compute $Q(v)$ for each vertex in topological order using the recurrence:

with the base case $Q(\mathbf{s}) = 1$.

Let us compute the quality-score for each of the 9 vertices:

1. Vertex $\mathbf{s}$:

   $$Q(\mathbf{s}) = 1$$

2. Vertex $a$:

   $$Q(a) = Q(\mathbf{s}) \times w(\mathbf{s}, a) = 1 \times 9 = 9$$

3. Vertex $b$:

   $$Q(b) = Q(a) \times w(a, b) = 9 \times 1 = 9$$

4. Vertex $c$:

   $$Q(c) = Q(\mathbf{s}) \times w(\mathbf{s}, c) = 1 \times 1 = 1$$

5. Vertex $d$: Incoming edges are from $c$ and $a$:

   • From $c$: $Q(c) \times w(c, d) = 1 \times 1 = 1$

   • From $a$: $Q(a) \times w(a, d) = 9 \times 1 = 9$

   $$Q(d) = \max(1, 9) = 9$$

6. Vertex $e$: Incoming edges are from $b$ and $d$:

   • From $b$: $Q(b) \times w(b, e) = 9 \times 1 = 9$

   • From $d$: $Q(d) \times w(d, e) = 9 \times 9 = 81$

   $$Q(e) = \max(9, 81) = 81$$

7. Vertex $f$:

   $$Q(f) = Q(c) \times w(c, f) = 1 \times 9 = 9$$

8. Vertex $g$: Incoming edges are from $f$ and $d$:

   • From $f$: $Q(f) \times w(f, g) = 9 \times 1 = 9$

   • From $d$: $Q(d) \times w(d, g) = 9 \times 9 = 81$

   $$Q(g) = \max(9, 81) = 81$$

9. Vertex $t$: Incoming edges are from $g$ and $e$:

   • From $g$: $Q(g) \times w(g, t) = 81 \times 1 = 81$

   • From $e$: $Q(e) \times w(e, t) = 81 \times 9 = 729$

   $$Q(t) = \max(81, 729) = 729$$

Sum of the quality-scores of all vertices:$$\begin{aligned} \text{Sum} &= Q(\mathbf{s}) + Q(a) + Q(b) + Q(c) + Q(d) + Q(e) + Q(f) + Q(g) + Q(t) \\ &= 1 + 9 + 9 + 1 + 9 + 81 + 9 + 81 + 729 \\ &= 929 \end{aligned}$$