1685. The Heaviest Route Through Each Stage

A DIRECTED graph of n vertices and m arrows has NO directed cycle, and each arrow carries a weight which may be NEGATIVE. A route may START and END anywhere, and a single vertex on its own counts as a route of weight 0.

For every vertex, print the LARGEST total weight of a route that passes through it, on one line separated by single spaces.

4 vertices 1 -> 2 (1) 2 -> 4 (1) 1 -> 3 (5) 3 -> 4 (5) -> 10 2 10 10

The heaviest route in the graph is 1 -> 3 -> 4 at 10, so vertices 1, 3 and 4 all report 10. Vertex 2 is only on 1 -> 2 -> 4, which weighs 2.

## The four things that have to be said

directed? yes. self-loops? impossible: a self-loop is a cycle and the input is acyclic. parallel arrows? allowed, at different weights, and the heavier copy wins. unreachable? no sentinel is needed anywhere, and that is the shape of this problem rather than an oversight: every vertex is on at least the route consisting of itself, of weight 0. A vertex with no arrows at all therefore reports 0, and so does a vertex whose only arrows are negative. When n is 1 the answer is the single number 0.

## What most people try first

Running problem 1679 from every vertex, which is n sweeps and O(n * (n + m)) work, and does not even answer the question: a sweep from v finds the heaviest route STARTING at v and knows nothing about what led into it.

The second instinct is to find the single heaviest route in the graph and report its weight for the vertices on it and 0 for the rest. That is wrong because a vertex off the heaviest route is usually on some lighter route, and the question asks for the best through EACH vertex. On the example vertex 2 answers 2, not 0.

## Two sweeps, then one addition per vertex

``` in[v] = the heaviest route ENDING at v, at least 0 out[v] = the heaviest route STARTING at v, at least 0

forward over the topological order: in[v] = max(in[v], in[u] + w) for u -> v backward over the same order: out[u] = max(out[u], out[v] + w) for u -> v

answer for v = in[v] + out[v] ```

Both arrays start at 0 everywhere, which encodes "the route consisting of this vertex alone", and is why a negative arrow is simply never taken.

## Why adding the two halves counts each route once and correctly

Every route through v splits at v into the part ending at v and the part starting at v, and the split is unique because the graph is acyclic and so a route cannot visit v twice. The two parts are independent: any route ending at v can be followed by any route starting at v, and the result is a route, again because acyclicity rules out the two halves meeting anywhere else.

So the heaviest route through v is the heaviest ending half plus the heaviest starting half, and the maximum of a sum of independent choices is the sum of the maxima. Nothing is double counted because v itself contributes no weight, weights being on the arrows.

The same argument on a graph with cycles fails at the first step, which is the real reason this problem states acyclicity rather than merely finding it convenient.

## Why the backward sweep needs no reversed graph

Read the topological order backwards and every arrow points backwards, which is a topological order of the reversed graph. So iterating the ORIGINAL adjacency lists in reverse vertex order visits every arrow u -> v only after out[v] is final, which is exactly what the recurrence needs.

## How this differs from problem 1706

Problem 1706 puts the weights on the VERTICES and asks for one number, the heaviest route anywhere in the graph. This puts them on the ARROWS and asks for one number per vertex, which needs the backward sweep that 1706 never performs. Problem 1670 asks the same per-vertex question about SHORTEST routes between a fixed pair, where the condition becomes an equality rather than a sum.

## Overflow, computed rather than assumed

A route in an acyclic graph is simple, so each half uses at most n - 1 = 49999 arrows of magnitude up to 10^6, reaching 5 * 10^10. Their SUM therefore reaches about 10^11, which is the quantity to watch and is far past the 2147483647 a signed 32 bit integer holds. Both arrays and the printed sum need 64 bits; a signed 64 bit integer holds 9223372036854775807, so 10^11 is nowhere near its limit.

## Cost

O(n + m): one topological sort, two sweeps, one scan. Memory O(n + m).

Constraints - `1 ≤ n ≤ 50000` - `0 ≤ m ≤ 100000` - `1 ≤ u, v ≤ n` - `-1000000 ≤ w ≤ 1000000` - The graph has no directed cycle.