New update is available. Click here to update.

Topics

Given array ‘PAR’ of size ‘N’, representing a binary tree, where ‘PAR[i]’ denotes the parent of node ‘i’. And a binary array ‘LOCK’ of ‘N’ integers, ‘LOCK[i] = 1’ means the ‘ith’ node is locked. Find out whether a target node ‘K’ can be locked or not.

A node will be locked only when some or all of the ancestors or the node itself is locked.

```
Input:
'N' = 5, ‘K’ = 3
‘ARR’ = [-1, 0, 0, 1, 2]
‘LOCK’ = [0, 0, 1, 0, 0]
Output: ‘1’
```

```
In the above tree in the simple path from node ‘4’ to root ‘1,’ the nodes encountered are [0, 1, 3], and no node from the set is locked. Hence node ‘3’ can be locked.
```

Detailed explanation

```
1 <= 'T' <= 10
1 <= 'N' <= 10^5
0 <= ‘K’ <= ‘N-1’
0 <= ‘PAR[i]’ <= ‘N-1’
0 <= ‘LOCK[i]’ <= 1
Time Limit: 1 sec
```

```
2
5 0
-1 0 3 0 3
1 1 1 0 0
4 1
3 2 -1 1
1 0 0 1
```

```
0
1
```

```
In the first test case,
```

```
In the above tree the target node ‘0’ is itself locked, so it cannot be locked.
Hence the answer is ‘false’.
In the second test case,
```

```
In the above tree in the simple path from node ‘1’ to root ‘2’ the nodes encountered are [1, 2], and no node from the set is locked.
Hence the answer is ‘true’.
```

```
2
4 2
-1 0 1 1
0 1 0 0
4 3
-1 0 1 2
1 0 0 0
```

```
0
0
```