We extend the definition of tridendriform bialgebra by introducing a parameter q. The subspace of primitive elements of a q-tridendriform bialgebra is equipped with an associative product and a natural structure of brace algebra, related by a distributive law. This data is called q-Gerstenhaber-Voronov algebras. We prove the equivalence between the categories of conilpotent q-tridendriform bialgebras and of q-Gerstenhaber-Voronov algebras. The space spanned by surjective maps between finite sets, as well as the space spanned by parking functions, have a natural structure of q-tridendriform bialgebra, denoted ST(q) and PQSym(q)*, in such a way that ST(q) is a sub-tridendriform bialgebra of PQSym(q)*. Finally we show that the bialgebra of M-permutations defined by T. Lam and P. Pylyavskyy comes from a q-tridendriform algebra which is a quotient of ST(q). (C) 2010 Elsevier Inc. All rights reserved.