The runtime of this test is linear in the number of nodes of D. In a lexicalized LCFRS extracted from a dependency treebank, there is a one-to-one correspondence between the blocks of a node u and the components of the template of the yield function f extracted for u.
the fan-out of f is exactly the block-degree of u.