As the title. The dynamic algorithm maintains the transitive closure of a tree when the tree undergoes a series of edge insertions (but no deletions)? And the algorithm supports constant query time.The paper (G.F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(23):273281, 1986.) introduces an algorithm for maintaining the transitive closure of a graph with O(n) amortized time pre  insertion. I wonder whether better algorithm exists for trees?
What is the fastest deterministic algorithm for incremental dynamic tree reachability?
ds.algorithms;graph theory;ds.data structures;dynamic algorithms