How to aggregate over a "multi source" with recursive, in postgres?
It took a while, but I figured it out:

WITH RECURSIVE
initial AS (
    SELECT
        department_name,
        department_name,
        FALSE
    FROM
        budgets
    GROUP BY department_name
),
tmp (child, parent, root) AS (
    SELECT
        *
    FROM
        initial
    UNION ALL
        SELECT
            tmp.child,
            CASE WHEN
                departments.parent_department IS NULL THEN tmp.parent
                ELSE departments.parent_department
            END,
            departments.parent_department IS NULL
        FROM
            tmp
            INNER JOIN departments
                ON tmp.parent = departments.name
        WHERE
            NOT tmp.root
)
SELECT
    tmp.parent,
    SUM(budget)
FROM
    tmp
    INNER JOIN budgets
        ON tmp.child = budgets.department_name
WHERE
    tmp.root
GROUP BY tmp.parent