Operations On Tree

Implement LockingTree for a rooted tree described by parent. Node 0 is the root and has parent -1; every other entry identifies that node's parent. All nodes start unlocked.

• lock(num, user) locks num for user if that node is currently unlocked. It does not check ancestors or descendants.
• unlock(num, user) unlocks num only if that same user currently owns its lock.
• upgrade(num, user) succeeds only when num is unlocked, every ancestor of num is unlocked, and at least one proper descendant is locked. On success, unlock every descendant regardless of its owner and lock num for user.

Each operation returns true when it succeeds and false otherwise. A failed operation leaves every lock unchanged. A proper descendant excludes the node itself.

Example 1:

Input: ["LockingTree","lock","unlock","upgrade","unlock","unlock"]
[[[-1,0,0]],[1,7],[1,8],[0,4],[1,7],[0,4]]

Output: [null,true,false,true,false,true]

Explanation: User 7 locks node 1; user 8 cannot unlock it. Upgrading root 0 succeeds because it has a locked descendant and no locked ancestor. This clears node 1 and locks node 0 for user 4, so only the final unlock succeeds.

Example 2:

Input: ["LockingTree","lock","lock","upgrade","unlock","upgrade"]
[[[-1,0,1]],[0,1],[2,2],[1,3],[0,1],[1,3]]

Output: [null,true,true,false,true,true]

Explanation: Both ordinary lock calls succeed, even though node 0 is an ancestor of node 2. Upgrading node 1 initially fails because node 0 is locked. After unlocking node 0, the upgrade succeeds and clears node 2.

Example 3:

Input: ["LockingTree","upgrade","lock","upgrade","unlock","lock","upgrade","unlock"]
[[[-1,0,0]],[0,1],[0,1],[0,2],[0,1],[2,99],[1,3],[2,99]]

Output: [null,false,true,false,true,true,false,true]

Explanation: An upgrade with no locked descendant fails. An already locked node also cannot be upgraded. Finally, locked node 2 is a sibling of node 1, so upgrading node 1 fails and leaves node 2 locked; its owner can still unlock it.

Constraints:

• 2 <= parent.length <= 2000
• parent[0] == -1
• Every other parent is a valid node index, and parent describes a valid tree rooted at node 0.
• 0 <= num < parent.length
• 1 <= user <= 10000
• At most 2000 calls are made to lock, unlock, and upgrade combined.