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 path and develop a dynamic programming (DP) algorithm with 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 an isotonic minima assumption 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 present efficient polynomial-time algorithms for various special cases, such as with piecewise linear convex costs, having dominating fixed costs at parent nodes, and arborescences with restricted branching. Numerical experiments validate the computational advantage of our proposed algorithms over generic solvers.