Mixed integer nonlinear programs with binary coupling decisions naturally model selective coordination tasks where a fixed penalty is incurred whenever adjacent continuous variables differ. A prominent example is the classical Potts model, which is widely used in statistical inference. However, exact solvability remains theoretically challenging since the problem is NP hard on general graphs, and generic global optimization approaches such as branch and bound methods often lack worst case guarantees. In this paper, we resolve this computational bottleneck for arbitrary tree topologies. We propose an exact parametric dynamic programming algorithm that achieves polynomial oracle complexity when the node cost functions belong to a fixed degree weak Chebyshev space, a broad functional class that includes piecewise polynomials. For the widely used quadratic cost setting, we perform a refined analysis which improves the complexity exponent to a near quadratic bound.