The Longest Path With No Repeat Next Door
Each node carries a lowercase letter. A PATH is a sequence of distinct nodes where each consecutive pair is joined by an edge. A path is GOOD when no two CONSECUTIVE nodes on it carry the same letter.
Print the number of nodes on the longest good path. The path may run anywhere in the tree and is not required to pass through the root.
5 nodes in a star, letters abbbb -> 3 leaf, centre, another leaf
4 nodes, letters abab, edges 1-2 1-3 3-4 -> 2
## A path in a tree bends exactly once
Take any path and look at the node on it closest to the root. Call it the TOP. From the top the path runs down into at most two different child subtrees, and never comes back up.
So every path is one of:
· a single downward run from its top, or · two downward runs from its top, into two DIFFERENT children
Every path has exactly one top, so taking the best answer at each node and maximising over nodes counts every path once.
## The state
down[u] = the longest good path that starts at u and only goes downwards
A child c may be joined to u only when its letter differs:
down[u] = 1 + max over children c with letter[c] != letter[u] of down[c]
## Joining two children at the top
At u, take the two LARGEST values of down[c] among children with a differing letter. Call
them b1 and b2, using 0 when fewer than two qualify. Then the best path topped at u is
b1 + b2 + 1
the plus one being u itself. The answer is the largest of these over all nodes.
The two children must be DIFFERENT children. Taking the same child twice would fold a path back on itself, which is why this is a largest-and-second-largest and not twice the largest.
Note that the two children's letters are each compared against u, never against each other.
They are not adjacent on the path, so they are allowed to match.
## Why two numbers, not two passes
It is tempting to find the best child, then loop again for the second best. One pass is
enough: keep b1 and b2 and update them as each child is read. The second pass is not wrong,
but on a star with 100000 children the bookkeeping is easy to get subtly wrong, and the single
pass is not.
## Boundaries
A single node answers 1, since a path of one node has no consecutive pair to violate anything.
A tree where every letter is the same answers 1: no edge may ever be used.
## Cost
Time O(n). Space O(n).