Propagating node labels upwards in a tree
I understand your problem as follows (the best I could make of your presentation of it).

You have a tree rooted in node B. Each leaf is labeled wih
categories. Each other node is labeled with the categories of all
leaves below that node. The problem is to maintain proper labeling of
all nodes, when changing the labels of leaves or adding or removing
nodes from the tree.

The problem is easy when categories are added. You only have to
propagate new categories from where they are added up to the root.
The addition can come from adding a category to a leaf, or adding a
new node with its own categories as a leaf, or with the categories of
its daughters if it is an intermediate node.

The difficulty comes from removing categories, either by removing them
from a leaf, or by removing a node and all the nodes below it. The
difficulty comes from the fact that the categories it propagated
upward may still have to be kept somewhere on the path, because they are
provided by some other nodes.

However, this can be addressed very simply. Just keep a count of how
many times a category is provided to a node from the leafs below that
node. Then both addition and removal require only a bit of accounting.
You remove a category from the labeling of a node when its count falls to zero for that node.

Time complexity

The complexity analysis below is added by an edit from Billiska. It can only be partial since the OP did not clearly state how the structure is to be used. In particular, it seems that he also intends to add or remove whole subtrees. But the information needed for the purpose is available from the root of the subtrees (assuming categories have been propagated beforehand in subtrees to be added), so that operating on whole subtrees is very similar to operating on leaves.

Let the tree have depth of $d$.

Look-up category of a given node is $O(1)$ since the category information is always stored up-to-date for each node.

Add a category to a given leaf node is $O(d)$ since the count of that category has to be incremented for every ancestor node up to the root.

Remove a category from a given leaf node is $O(d)$. Just the revert of add, we decrements the count of that category for every ancestor node up to the root.