Algorithm: 1-Crossing Trees
l Compute edges’ LCA’s: O(m)
l Compute “cuts” at leaves
» Cut values = degrees
» each edge incident on at most two leaves
» total time O(m)
l Dynamic program upwards: O(n)
Total: O(m+n)