What is the fastest deterministic algorithm for incremental dynamic tree reachability?
The best I can find for this is $O(\log n)$ amortized update time with constant query time. The basic idea is that if you know both preorder and postorder for a tree, you can recover reachability: there is a path from $x$ to $y$ iff $x$ is before $y$ in preorder and after it in postorder.

There are several data structures that can maintain a list of items, allowing insertions immediately before or after one particular item, deletions, and constant time ordering queries, in constant time per operation; see e.g. http://erikdemaine.org/papers/DietzSleator_ESA2002/paper.pdf. Record for each node which tree it belongs to, and use one of these structures for the preorder and postorder of each tree. If these structures do not already do this for you, also use a linked list so you can read off the tree nodes in either order.

To add an edge from a node $x$ to a node $y$ (where prior to the addition, $y$ is the root of a tree) we need to merge the orderings for two trees. Do so by finding which of the two trees is smaller, adding its vertices into the ordering structures for the tree that is larger, and changing the node labels on the nodes in the smaller tree to point to the larger one. In this way, each vertex participates in $O(\log n)$ updates over the lifetime of the structure (every time it is part of the smaller tree, the size of the tree it is in doubles). More precisely, each tree with $k$ edges takes total time $O(k\log k)$ to build, so the amortized time per edge is logarithmic.