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