Fibonacci Paths

Every directed edge is automatically valid. That is the freebie: a generalized Fibonacci sequence of length $2$ has arbitrary first two numbers, so there is no recurrence condition yet.

The real job is counting longer paths without doing some horrifying exponential path search. Spoiler: the graph can have cycles, but the values save us.

Edge DP

A valid path only needs its last two values to know what can come next. So use directed edges as DP states.

For an edge $u\to v$, define

$dp[u,v] = \text{number of valid paths whose last two vertices are exactly } u,v.$

The path can be just the two vertices $(u,v)$, so every edge contributes at least $1$:

$dp[u,v] \ge 1.$

Now suppose a longer valid path ends with

$\dots,p,u,v.$

Then the Fibonacci rule forces

$a_v = a_p + a_u.$

So, for a fixed edge $u\to v$, the previous vertex $p$ must satisfy

$a_p = a_v-a_u$

and there must be an edge $p\to u$.

Therefore:

$dp[u,v] = 1 + \sum_{p\to u,\ a_p=a_v-a_u} dp[p,u].$

If $a_v\le a_u$, then $a_v-a_u$ is not positive, so there is no previous natural value. In that case $dp[u,v]=1$.

That recurrence is the whole problem. Everything else is just making it fast.

Why the order works

Any non-base transition into $u\to v$ uses some previous edge $p\to u$ with

$a_v=a_p+a_u.$

Since all values are positive,

$a_v>a_u.$

So the previous DP state has destination value $a_u$, while the current one has destination value $a_v$, and $a_u<a_v$.

That means we can sort all directed edges by the value of their destination vertex and process them in that order. When we compute $dp[u,v]$, every possible $dp[p,u]$ has already been computed.

No cycle drama. The values are doing the topological sort for us.

Fast grouped sums

The recurrence asks for:

$\sum_{p\to u,\ a_p=x} dp[p,u]$

for one specific value $x=a_v-a_u$.

So for each vertex $u$, maintain a table:

$sum[u][x] = \sum_{p\to u,\ a_p=x} dp[p,u]$

using only edges already processed.

When processing edge $u\to v$:

1. Start with $ways=1$ for the length-$2$ path $(u,v)$.
2. If $a_v>a_u$, add $sum[u][a_v-a_u]$.
3. Add $ways$ to the answer.
4. Update $sum[v][a_u] += ways$, because this edge can now become the previous edge for future paths.

To avoid hash-map shenanigans, we can coordinate-compress separately per vertex. For every incoming edge $p\to u$, the only key ever needed in $sum[u]$ from that edge is $a_p$. Store all such values for each vertex, sort and unique them, and use binary search.

About the “simple path” condition

This part looks scary, but it is basically bait.

For a valid sequence

$x_0,x_1,x_2,\dots,$

we have

$x_2=x_0+x_1>x_0,x_1,$

and after that the sequence strictly increases. So values cannot repeat, except possibly $x_0=x_1$ at the first two positions.

The first two vertices still cannot be the same vertex because the input has no self-loops. After that, every new value is larger than the previous relevant values, so no vertex can reappear. Thus every Fibonacci-valued directed walk counted here is already simple. Nice for us; mildly rude of the statement to make it sound worse.

Correctness proof

We prove that the algorithm counts exactly the valid paths.

First, every edge $u\to v$ is initialized with one path, namely $(u,v)$. This is valid because any two positive numbers form a generalized Fibonacci sequence of length $2$.

Now consider a DP contribution added to $dp[u,v]$ from some previous edge $p\to u$. The algorithm only adds it when $a_p=a_v-a_u$, which is equivalent to $a_v=a_p+a_u$. Therefore appending $v$ to any valid path ending in $(p,u)$ preserves the Fibonacci recurrence. Since $u\to v$ is an actual directed edge, the result is a valid directed path.

Conversely, take any valid path of length at least $3$ ending in $p,u,v$. Its prefix ending in $p,u$ is also valid, and the recurrence gives $a_p=a_v-a_u$. When the algorithm processes $u\to v$, the value $dp[p,u]$ is included in $sum[u][a_p]$, so this path is counted.

The processing order is valid because every transition goes from destination value $a_u$ to destination value $a_v$, and $a_v>a_u$. Sorting edges by destination value guarantees all required previous states are ready.

Finally, the counted walks are simple because positive Fibonacci growth prevents repeated values after the first two positions, and self-loops do not exist. So the algorithm counts exactly the required simple paths.

Complexity

For each test case, we sort the $m$ edges and sort the per-vertex key lists. Each edge does a constant number of binary searches in its vertex-local list.

Total complexity:

$O(m\log m)$

Memory:

$O(n+m).$