You seem to have answered you own question. Have each node hold the count of its descendents plus one (itself). Every time you remove a node you decrement each count on the path back to the root. When inserting you instead increment each count on that path. This way each node contains the total number of nodes in its sub-tree. This will work fine for n-ary trees.

You can even perform the increment/decrement on the way down the tree if you are sure that the node you are inserting/deleting doesn't/does exist.

You seem to have answered you own question. Have each node hold the count of its descendents plus one (itself). Every time you remove a node you decrement each count on the path back to the root. When inserting you instead increment each count on that path. This way each node contains the total number of nodes in its sub-tree. This will work fine for n-ary trees.

You can even perform the increment/decrement on the way down the tree if you are sure that the node you are inserting/deleting doesn't/does exist.

EDIT: Removing a node in the middle of the tree. Say you have a tree (labeled with the counts):

     |
    A(a)
   /   \
 B(b)  C(c)

Let's say you delete A and the rules say B should move up to fill it's place. As we said before you would decrement the counts on the path to the root, but you also need to update B's count as it is the new root of the subtree. You have to add C's count to B's:

     |
   B(b+c)
  /     \
...    C(c)