level_ancestor (588B)
1 # Level ancestor 2 3 Do [preprocessing] on [tree] and compute [data_structure] such that given a [node] and integer d you can find the [ancestor] of the [node] at distance d from it (or, equivalently, at specified [depth]) 4 5 Can be done with linear preprocessing of the tree and constant query time 6 - cf for instance [bender2004level] 7 - [alstrup2000improved] for [trees] under [updates], and to find the node with minimum weight on the path between two nodes when the tree is weighted 8 - [bender2003level]: simplified version of the problem (decompose into [microtrees]) 9 10 Up: [data_structure]