6 NP-hard (Desper and Gascuel, 2005) if u is allowed to be an arbitrary undirected tree.
if we restrict u to be in U, as we do in the above, then maximizingĉ(u) over U can be solved using the bilexical parsing algorithm from Eisner and Satta (1999).