The oracle is very efficient, computing loss in O(n), compared to O(n 8 ) for the only previously known dynamic oracle with support for a subset of non-projective trees (Gómez-Rodríguez et al., 2014).
to do so, we can implement WEAKLYCONNECtED so that the first call computes the connected components of A in linear time (Hopcroft and tarjan, 1973) and subsequent calls use this information to find out if two nodes are weakly connected in constant time.