Operations on Tree

Design a data structure for a rooted tree that supports lock(num,user), unlock(num,user) and upgrade(num,user) operations where lock/unlock enforce ownership, and upgrade locks a node only if it is unlocked, has at least one locked descendant (by any user), and has no locked ancestors — then it unlocks all descendants. The core challenge is efficiently checking and updating ancestor/descendant lock status (and mass-unlocking descendants) across many operations.