A Tree with User-Owned Locks

### Problem Implement `LockingTree` on a valid parent-array tree rooted at node 0. `lock(num,user)` succeeds exactly when that node is unlocked and then records its owner. `unlock(num,user)` succeeds only for its current owner. `upgrade(num,user)` succeeds only if the target is unlocked, has no locked strict ancestor and has at least one locked strict descendant. A successful upgrade locks the target for the given user and unlocks all descendants regardless of their owners. A failed operation changes no lock state. ```cpp class LockingTree { public: LockingTree(vector<int>& parent); bool lock(int num, int user); bool unlock(int num, int user); bool upgrade(int num, int user); }; ``` ### Examples **Example 1:** ```text parent = [-1,0,0] Calls: lock(1,4), upgrade(0,7), unlock(1,4), unlock(0,7) Results: true, true, false, true Explanation: The upgrade clears node 1 and gives node 0 to user 7. ``` **Example 2:** ```text parent = [-1,0,1] Calls: lock(0,2), lock(2,3), upgrade(1,4), unlock(0,5) Results: true, true, false, false Explanation: Ordinary lock ignores ancestors; upgrade is blocked by locked ancestor 0, and user 5 does not own node 0. ``` ### Constraints - `2 <= parent.length <= 2000`; `parent[0] == -1`. - Other parent values and num are valid node indices; parent represents a tree. - `1 <= user <= 10^4`; at most 2000 total method calls. ### Clarifying Questions Only upgrade checks ancestors and descendants. Ordinary lock checks the target alone. Descendants and ancestors exclude the target itself. ```hint Inspect the structure Which checks must finish before upgrade changes any ownership? ``` ### Reasoning checkpoints - Keep ownership and state transitions correct across sequences of lock, unlock and upgrade calls. - Apply all three upgrade conditions before making changes, including descendants owned by other users. - Preserve the distinction between ordinary lock permissions and the stricter upgrade preconditions. ### Optional extensions How could you accelerate descendant-lock checks and clearing operations on a much larger tree?