 |
 |
14 of 18 |  |
 |
 |
MIT
Algorithm: 1-
Respected Trees
l
Compute edge’s
LCA’s
: O
(m
)
l
Compute “cuts” at leaves
»
each edge on at most two leaves
»
total
O(m)
l
treefix
upwards: O
(n)
l
Total: O(m+n)