576. The Longest Rising Chain Downwards

Each node of a tree holds a value. The tree is rooted at node 1. A CHAIN is a sequence of nodes where each one is the parent of the next, and the values strictly increase along it.

Print the number of nodes in the longest chain.

5 nodes in a path, values 1 2 3 4 5 -> 5 4 nodes, values 3 2 1 5, edges 1-2 1-3 3-4 -> 2 nodes 3 and 4

## Only downwards

A chain goes one way: from an ancestor towards a descendant. It never turns a corner and it never goes up. That restriction is what keeps the state to a single number per node, and it is what separates this problem from 577, where the path may bend.

## One number per node

down[u] = the longest chain that STARTS at u and goes downwards

A child c extends a chain from u only when value[c] > value[u]. So:

down[u] = 1 + max over children c with value[c] > value[u] of down[c]

and down[u] = 1 when no child qualifies.

The answer is the largest down[u] over all nodes, not down[root]. The best chain may start anywhere, and on the first sample it starts at node 3.

## The reset is the point

When a child's value is not larger, the chain does not shorten or carry over: it simply does not extend, and the child begins a fresh chain of its own. That is the same reset as in a run-length scan over an array, which is why this state is called linear even though it lives on a tree.

Reading a child's down without the value test is the classic bug here, and it reports a chain that is not increasing.

## Strictly increasing

Equal values do NOT extend a chain. A tree where every value is identical answers 1, and the tests include one.

## Boundaries

A single node answers 1: it is a chain of length one by itself.

A tree whose values decrease all the way down also answers 1, which is the case that distinguishes a correct maximum over all nodes from a maximum taken only at the root.

## Cost

Time O(n). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ each value ≤ 10^9` - the input is always a tree