In a recent note we presented a compact formula for the complete tree-level S-matrix of pure Yang-Mills and gravity theories in arbitrary spacetime dimension. In this paper we show that a natural formulation also exists for a massless colored cubic scalar theory. In Yang-Mills, the formula is an integral over the space of n marked points on a sphere and has as integrand two factors. The first factor is a combination of Parke-Taylor-like terms dressed with U( N ) color structures while the second is a Pfaffian. The S-matrix of a U( N ) × U( Ñ ) cubic scalar theory is obtained by simply replacing the Pfaffian with a U( Ñ ) version of the previous U( N ) factor. Given that gravity amplitudes are obtained by replacing the U( N ) factor in Yang-Mills by a second Pfaffian, we are led to a natural color-kinematics correspondence. An expansion of the integrand of the scalar theory leads to sums over trivalent graphs and are directly related to the KLT matrix. Combining this and the Yang-Mills formula we find a connection to the BCJ color-kinematics duality as well as a new proof of the BCJ doubling property that gives rise to gravity amplitudes. We end by considering a special kinematic point where the partial amplitude simply counts the number of color-ordered planar trivalent trees, which equals a Catalan number. The scattering equations simplify dramatically and are equivalent to a special Y-system with solutions related to roots of Chebyshev polynomials. The sum of the integrand over the solutions gives rise to a representation of Catalan numbers in terms of eigenvectors and eigenvalues of the adjacency matrix of an A -type Dynkin diagram.