You are given a tree with n nodes numbered from 0 to n - 1 in the form of a parent array parent where parent[i] is the parent of the ith node. The root of the tree is node 0, so parent[0] = -1 since it has no parent. You want to design a data structure that allows users to lock, unlock, and upgrade nodes in the tree.
The data structure should support the following functions:
- Lock: Locks the given node for the given user and prevents other users from locking the same node. You may only lock a node using this function if the node is unlocked.
- Unlock: Unlocks the given node for the given user. You may only unlock a node using this function if it is currently locked by the same user.
- Upgrade: Locks the given node for the given user and unlocks all of its descendants regardless of who locked it. You may only upgrade a node if all 3 conditions are true:
- The node is unlocked,
- It has at least one locked descendant (by any user), and
- It does not have any locked ancestors.
Implement the LockingTree class:
LockingTree(int[] parent)initializes the data structure with the parent array.lock(int num, int user)returnstrueif it is possible for the user with iduserto lock the nodenum, orfalseotherwise. If it is possible, the nodenumwill become locked by the user with iduser.unlock(int num, int user)returnstrueif it is possible for the user with iduserto unlock the nodenum, orfalseotherwise. If it is possible, the nodenumwill become unlocked.upgrade(int num, int user)returnstrueif it is possible for the user with iduserto upgrade the nodenum, orfalseotherwise. If it is possible, the nodenumwill be upgraded.
Example 1:
Input ["LockingTree", "lock", "unlock", "unlock", "lock", "upgrade", "lock"] [[[-1, 0, 0, 1, 1, 2, 2]], [2, 2], [2, 3], [2, 2], [4, 5], [0, 1], [0, 1]] Output [null, true, false, true, true, true, false]Explanation LockingTree lockingTree = new LockingTree([-1, 0, 0, 1, 1, 2, 2]); lockingTree.lock(2, 2); // return true because node 2 is unlocked. // Node 2 will now be locked by user 2. lockingTree.unlock(2, 3); // return false because user 3 cannot unlock a node locked by user 2. lockingTree.unlock(2, 2); // return true because node 2 was previously locked by user 2. // Node 2 will now be unlocked. lockingTree.lock(4, 5); // return true because node 4 is unlocked. // Node 4 will now be locked by user 5. lockingTree.upgrade(0, 1); // return true because node 0 is unlocked and has at least one locked descendant (node 4). // Node 0 will now be locked by user 1 and node 4 will now be unlocked. lockingTree.lock(0, 1); // return false because node 0 is already locked.
Constraints:
n == parent.length2 <= n <= 20000 <= parent[i] <= n - 1fori != 0parent[0] == -10 <= num <= n - 11 <= user <= 104parentrepresents a valid tree.- At most
2000calls in total will be made tolock,unlock, andupgrade.
DFS.
class LockingTree:
def __init__(self, parent: List[int]):
self.nums = {}
self.parent = parent
self.children = defaultdict(list)
for i, p in enumerate(parent):
self.children[p].append(i)
def lock(self, num: int, user: int) -> bool:
if num in self.nums:
return False
self.nums[num] = user
return True
def unlock(self, num: int, user: int) -> bool:
if num not in self.nums or self.nums[num] != user:
return False
self.nums.pop(num)
return True
def upgrade(self, num: int, user: int) -> bool:
def dfs(num):
nonlocal find
for child in self.children[num]:
if child in self.nums:
self.nums.pop(child)
find = True
dfs(child)
t = num
while t != -1:
if t in self.nums:
return False
t = self.parent[t]
find = False
dfs(num)
if not find:
return False
self.nums[num] = user
return True
# Your LockingTree object will be instantiated and called as such:
# obj = LockingTree(parent)
# param_1 = obj.lock(num,user)
# param_2 = obj.unlock(num,user)
# param_3 = obj.upgrade(num,user)class LockingTree {
private Map<Integer, Integer> nums;
private int[] parent;
private List<Integer>[] children;
public LockingTree(int[] parent) {
nums = new HashMap<>();
this.parent = parent;
int n = parent.length;
children = new List[n];
for (int i = 0; i < n; ++i) {
children[i] = new ArrayList<>();
}
for (int i = 0; i < n; ++i) {
if (parent[i] != -1) {
children[parent[i]].add(i);
}
}
}
public boolean lock(int num, int user) {
if (nums.containsKey(num)) {
return false;
}
nums.put(num, user);
return true;
}
public boolean unlock(int num, int user) {
if (!nums.containsKey(num) || nums.get(num) != user) {
return false;
}
nums.remove(num);
return true;
}
public boolean upgrade(int num, int user) {
int t = num;
while (t != -1) {
if (nums.containsKey(t)) {
return false;
}
t = parent[t];
}
boolean[] find = new boolean[1];
dfs(num, find);
if (!find[0]) {
return false;
}
nums.put(num, user);
return true;
}
private void dfs(int num, boolean[] find) {
for (int child : children[num]) {
if (nums.containsKey(child)) {
nums.remove(child);
find[0] = true;
}
dfs(child, find);
}
}
}
/**
* Your LockingTree object will be instantiated and called as such:
* LockingTree obj = new LockingTree(parent);
* boolean param_1 = obj.lock(num,user);
* boolean param_2 = obj.unlock(num,user);
* boolean param_3 = obj.upgrade(num,user);
*/class LockingTree {
public:
unordered_map<int, int> nums;
vector<int> parent;
vector<vector<int>> children;
LockingTree(vector<int>& parent) {
this->parent = parent;
int n = parent.size();
children.resize(n);
for (int i = 0; i < n; ++i)
if (parent[i] != -1)
children[parent[i]].push_back(i);
}
bool lock(int num, int user) {
if (nums.count(num)) return false;
nums[num] = user;
return true;
}
bool unlock(int num, int user) {
if (!nums.count(num) || nums[num] != user) return false;
nums.erase(num);
return true;
}
bool upgrade(int num, int user) {
for (int t = num; t != -1; t = parent[t])
if (nums.count(t))
return false;
bool find = false;
dfs(num, find);
if (!find) return false;
nums[num] = user;
return true;
}
void dfs(int num, bool& find) {
for (int child : children[num])
{
if (nums.count(child))
{
nums.erase(child);
find = true;
}
dfs(child, find);
}
}
};
/**
* Your LockingTree object will be instantiated and called as such:
* LockingTree* obj = new LockingTree(parent);
* bool param_1 = obj->lock(num,user);
* bool param_2 = obj->unlock(num,user);
* bool param_3 = obj->upgrade(num,user);
*/type LockingTree struct {
nums map[int]int
parent []int
children [][]int
}
func Constructor(parent []int) LockingTree {
n := len(parent)
nums := make(map[int]int)
children := make([][]int, n)
for i, p := range parent {
if p != -1 {
children[p] = append(children[p], i)
}
}
return LockingTree{nums, parent, children}
}
func (this *LockingTree) Lock(num int, user int) bool {
if _, ok := this.nums[num]; ok {
return false
}
this.nums[num] = user
return true
}
func (this *LockingTree) Unlock(num int, user int) bool {
if this.nums[num] != user {
return false
}
delete(this.nums, num)
return true
}
func (this *LockingTree) Upgrade(num int, user int) bool {
for t := num; t != -1; t = this.parent[t] {
if _, ok := this.nums[t]; ok {
return false
}
}
find := false
var dfs func(int)
dfs = func(num int) {
for _, child := range this.children[num] {
if _, ok := this.nums[child]; ok {
delete(this.nums, child)
find = true
}
dfs(child)
}
}
dfs(num)
if !find {
return false
}
this.nums[num] = user
return true
}
/**
* Your LockingTree object will be instantiated and called as such:
* obj := Constructor(parent);
* param_1 := obj.Lock(num,user);
* param_2 := obj.Unlock(num,user);
* param_3 := obj.Upgrade(num,user);
*/