First, we use DSU in order to store current companies after each merge. For each company we also store a map: the degree of the root (at most D) to the minimal depth of the tree with that degree. Initially all trees contain 1 vertex and all maps contain the pair (0, 1) only. Calculating this map for a new company after merge is simple: we just trying to connect the first root to the second one and vice versa, for all values of the degree of parent root. In a such way the new degree is increased by 1 and the new depth is at most the minimal depth of child root's tree increased by 1.