Как организовать оптимальное хранение ошибок в иерархической структуре?
Как-то так: pastebin.com/K6Z8JqVT
То есть, идея в том, чтобы подписать узел на событие изменения состояния "маркера" при его добавлении в узел. При этом, узел распространяет события своему родителю (если он есть) вплоть до корневого. Каждый узел хранит компактный набор счетчиков состояний, связанных с его "маркерами" и "маркерами" дочерних узлов. Что-то еще более оптимизировать, на мой взгляд, смысла нет, т.к. TreeMap (O(nlog(n)) с ключом по состоянию -- это и так очень быстро. 
Код, разумеется, не thread-safe.
Насколько часто приходится вычислять состояния и сколько объектов?
Надо смотреть на конкретных примерах, но любая оптимизация за счет доп. словарей будет требовать больше памяти. По моему мнению, если вычисление состояния долгая операция, то можно сделать так, надежнее будет скомбинировать подписку на событие изменения состояния дочерних элементов и вычисление общего состояния при каждом изменении:
Подписываем узел на событие "ИзменениеСостояния" у дочерних узлов. Каждый узел распространяет событие своему родителю, вплоть до корневого. В каждом узле храним признак "isActualState", = "true" если дочерние узлы НЕ оповещали об изменении состояния, = "false" если хотя бы один из дочерних узлов оповестил. После генерации события, происходит перерасчет состояния с повторным вычислением состояния только в той ветке, где реально были изменения (isActualState=false), а от всех остальных будет использоваться текущее хранимое состояние.