print$("$Hello World"$)$

import sys

from collections import deque

class Node:

def $\_\_$init$\_\_($self$,$ v$,$ parent$=$None$)$:

self.v $=$ v

self.children $=[]$

self.parent $=$ parent

self.ancestor$\_$locked $=0$

self.descendant$\_$locked $=0$

self.user$\_$id $=0$

self.is$\_$locked $=$ False

def add$\_$children$($self$,$ child$\_$labels, parent$\_$node$)$:

for child$\_$label in child$\_$labels:

self.children.append$($Node$($child$\_$label, parent$\_$node$))$

def build$\_$tree$($root$,$m$,$nodes$)$:

q$=$ deque$([$root$])$

st$=1$

while q:

r$=$q$.$popleft$()$

if st $>=$ len$($nodes$)$:

continue

temp $=$ nodes$[$st:st$+$m$]$

r$.$add$\_$children$($temp$,$r$)$

st $+=$ m

for link in r$.$children:

q$.$append$($link$)$

return root

class Tree:

def $\_\_$init$\_\_($self$,$ tree$\_$root$)$:

self.root $=$ tree$\_$root

self.vton $=\{\}$

self.output$\_$log $=[]$

self.fill$\_$vton$($self$.$root$)$

def fill$\_$vton$($self$,$ current$\_$node$)$:

if not current$\_$node:

return

self.vton$[$current$\_$node.v$]=($current$\_$node, set$())$

for child in current$\_$node.children:

self.fill$\_$vton$($child$)$

def lock$\_$node$($self$,$ v$,$ id$)$:

t $=$ self.vton.get$($v$,($None$,))[0]$

if t$.$is$\_$locked or len$($self$.$vton$[$v$][1])!=0$ or t$.$descendant$\_$locked $!=0$:

return False

curr $=$ t$.$parent

while curr:

if curr.is$\_$locked:

return False

curr $=$ curr.parent

while curr:

curr.descendant$\_$locked $+=1$

self.vton$[$curr$.$v$][1].$add$($t$)$

curr $=$ curr.parent

t$.$is$\_$locked $=$ True

t$.$user$\_$id $=$ id

return True

def unlock$\_$node$($self$,$ v$,$ id$)$:

t $=$ self.vton.get$($v$,($None$,))[0]$

if not t or not t$.$is$\_$locked or t$.$user$\_$id $!=$ id:

return False

curr $=$ t$.$parent

while curr:

curr.descendant$\_$locked $-=1$

if t in self.vton$[$curr$.$v$][1]$:

self.vton$[$curr$.$v$][1].$remove$($t$)$

curr $=$ curr.parent

t$.$is$\_$locked $=$ False

return True

def upgrade$\_$node$($self$,$ v$,$ id$)$:

t $=$ self.vton.get$($v$,($None$,))[0]$

if not t or t$.$is$\_$locked or t$.$ancestor$\_$locked $!=0$ or t$.$descendant$\_$locked $==0$:

return False

locked$\_$descendants $=$ list$($self$.$vton$[$v$][1])$

for locked$\_$descendant in locked$\_$descendants:

if locked$\_$descendant.user$\_$id $!=$ id:

return False

for locked$\_$descendant in locked$\_$descendants:

self.unlock$\_$node$($locked$\_$descendant.v$,$ id$)$

self.lock$\_$node$($v$,$ id$)$

return True

if $\_\_$name$\_\_=="\_\_$main$\_\_"$:

import sys

input $=$ sys$.$stdin.read

data $=$ input$().$split$()$

n $=$ int$($data$[0])$

m $=$ int$($data$[1])$

q $=$ int$($data$[2])$

nodes $=$ data$[3$:$3+$ n$]$

queries $=$ data$[3+$ n:$]$

root $=$ Node$($nodes$[0],$ None$)$

root $=$ build$\_$tree$($root$,$ m$,$ nodes$)$

tree $=$ Tree$($root$)$

idx $=0$

results $=[]$

while idx $<$ len$($queries$)$:

op $=$ int$($queries$[$idx$])$

sv $=$ queries$[$idx $+1]$

uid $=$ int$($queries$[$idx $+2])$

idx $+=3$

if op $==1$:

results.append$("$true$"$ if tree.lock$\_$node$($sv$,$ uid$)$ else "false"$)$

elif op $==2$:

results.append$("$true$"$ if tree.unlock$\_$node$($sv$,$ uid$)$ else "false"$)$

elif op $==3$:

results.append$("$true$"$ if tree.upgrade$\_$node$($sv$,$ uid$)$ else "false"$)$

for result in results:

print$($result$)$

Make above code

Let$$s say you are running the lock$/$unlock in a multi core machine. Now you

want to let multiple threads to run lock$()$ As we saw in part A$,$ locking a

node has multiple validations inside. Will doing lock on two nodes

cause a race condition. If yes, how will you solve it$.$ In short, how do

make the lock$()$ function thread safe? $-$ Multiple threads running it

simultaneously shouldn$$t not affect the correctness. $-$ Try to make the

critical sections more granular. ie$.$ don$$t create any big

atomic$/$synchronised blocks that will make parallelism suffer. Consider

each operation is atomic.

if run in a multi$-$threaded$$machine

without using threading library $,$ by using valiables to make function mutually exclusive