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).