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
)