This paper introduces a generalized isotonic optimization framework over an arborescence graph, where each node incurs state-dependent convex costs and a fixed cost upon strict increases. We begin with the special case in which the arborescence is a directed path and develop a dynamic programming (DP) algorithm whose DP stage, excluding preprocessing, has an initial complexity of $O(n^3)$, which we improve to $O(n^2 \log n)$ by exploiting problem structure, and further to $O(n)$ under isotonic minima and constant-time block-data queries assumptions via the Monge property. For general arborescences, where the path-based DP is inapplicable, we identify structural conditions under which the problem remains tractable. In particular, we develop polynomial-time algorithms for cases with piecewise linear convex costs, dominating fixed costs at parent nodes, or arborescences of logarithmic height or bounded Horton–Strahler number, provided that sums of node costs can be minimized and their intersections with horizontal lines can be computed exactly in polynomial time. For general arborescences, we show tight worst-case bounds of $n^{\Theta(\log n)}$ on the number of convex pieces required to represent the parametric DP value functions. Numerical experiments on synthetic instances demonstrate the computational advantages of our proposed algorithms over the big-M baselines.