Sum tree with node values computed from children

A tree's leaves hold numbers, and every other node's value is the sum of its children. Return the value of any node. Then support changes: turn a node into a leaf with a value, or give a leaf a subtree so it becomes a parent. Keep queries fast after changes, for example by caching sums and updating the ancestors of whatever changed.