I'm interested in an algorithm which is able to compute reachability between any two nodes in polylog update (add or remove a valid edge) and query. I know that such an algorithm does exist for all undirected graphs and that no such algorithm exists for directed graphs. I'm wondering if such an algorithm exists for rooted directed trees.
