you give tree n node number 0 n 1 form parent array parent parenti parent ith node the root tree node 0 parent0 1 parent you want design datum structure allow user lock unlock upgrade node treethe data structure support follow functionsLock Locks give node give user prevent user lock node you lock node function node unlockedUnlock unlock give node give user you unlock node function currently lock userupgrade Locks give node give user unlock descendant regardless lock you upgrade node 3 condition truethe node unlockedIt lock descendant user andIt lock ancestorsimplement LockingTree classLockingTreeint parent initialize data structure parent arraylockint num int user return true possible user i d user lock node num false if possible node num lock user i d userunlockint num int user return true possible user i d user unlock node num false if possible node num unlockedupgradeint num int user return true possible user i d user upgrade node num false if possible node num upgrade Example 1inputlockingtree lock unlock unlock lock upgrade lock1 0 0 1 1 2 2 2 2 2 3 2 2 4 5 0 1 0 1outputnull true false true true true falseexplanationlockingtree lockingtree new LockingTree1 0 0 1 1 2 2lockingtreelock2 2 return true node 2 unlock Node 2 locked user 2lockingTreeunlock2 3 return false user 3 unlock node lock user 2lockingTreeunlock2 2 return true node 2 previously lock user 2 Node 2 unlockedlockingtreelock4 5 return true node 4 unlock Node 4 lock user 5lockingTreeupgrade0 1 return true node 0 unlocked lock descendant node 4 Node 0 lock user 1 node 4 unlockedlockingtreelock0 1 return false node 0 lock Constraintsn parentlength2 n 20000 parenti n 1 0parent0 10 num n 11 user 104parent represent valid treeat 2000 call total lock unlock upgrade