from math import ceil,log
def binpow(a,b):
res=1
while b > 0 :
if b & 1 :res = res * a
a *= a
b >>= 1
return res
class STree:
def __init__(self,arr):
self.arr_size = len(arr)-1
height=ceil(log(self.arr_size+1,2))
ST_size = ( 2 * binpow(2,height) ) - 1
self.ST=[None for _ in range(ST_size)]
self.build_ST(arr, 0, 0, self.arr_size)
def build_ST(self,arr,ind,L,R):
if L == R:
self.ST[ind] = arr[L]
return self.ST[ind]
mid = L + (R - L)//2
self.ST[ind]=self.build_ST(arr, ind*2+1, L, mid)+self.build_ST(arr, ind*2+2, mid+1, R)
return self.ST[ind]
def search_Query(self,L,R):
if L > R or L < 0 or R > self.arr_size:
return None
return self.search_Help( 0, 0, self.arr_size, L, R)
def search_Help(self, ind, start, end, L, R):
if L <= start and R >= end:
return self.ST[ind]
if end < L or start > R:
return 0
mid=(start+(end-start)//2)
return self.search_Help(2*ind+1,start,mid,L,R)+self.search_Help(2*ind+2,mid+1,end,L,R)
def update_Query(self, arr, ind, val):
if ind < 0 or ind > self.arr_size:
return None
diff=val-arr[ind]
arr[ind]=val
self.help_Update( 0, self.arr_size, ind, diff,0)
def help_Update(self, start, end, update_ind, diff, curr_ind):
if update_ind < start or update_ind > end:
return
self.ST[curr_ind] += diff
if start != end:
mid = start + (end-start)//2
self.help_Update(start, mid, update_ind, diff, curr_ind*2 +1)
self.help_Update(mid+1, end, update_ind, diff, curr_ind*2 +2)
class Graph:
def __init__(self,V):
self.V=V
self.graph=[[] for i in range(V+1)]
self.Visited=set()
self.count=0
self.intime=dict()
self.outtime=dict()
def addEdges(self):
self.weight=[int(x) for x in input().split()]
for _ in range(len(self.graph)-2):
u,v=map(int, input().split())
self.graph[u].append(v)
self.graph[v].append(u)
def DFS(self,Node):
self.intime[Node]=self.count
self.count+=1
self.Visited.add(Node)
for each in self.graph[Node]:
if each not in self.Visited:
self.DFS(each)
self.outtime[Node]=self.count
self.count+=1
def constructFlatt(self):
self.flatt=[0 for i in range(self.V*2)]
for i in range(1,self.V+1):
self.flatt[self.intime[i]]=self.weight[i-1]
self.flatt[self.outtime[i]]=(self.weight[i-1]*-1)
V, Q = map(int,input().split())
gra = Graph(V)
gra.addEdges()
gra.DFS(1)
gra.constructFlatt()
st = STree(gra.flatt)
for _ in range(Q):
ty, u, v = map(int, input().split())
if ty == 1:
u_In = gra.intime[u]
u_Out = gra.outtime[u]
v_In=gra.intime[v]
v_Out=gra.outtime[v]
if (u_In <= v_In <= u_Out) or (v_In <= u_In <= v_Out):
if u_In <= v_In:
print(st.search_Query(u_In, v_In))
else:
print(st.search_Query(v_In, u_In))
else:
print(-1)
else:
In=gra.intime[u]
Out=gra.outtime[u]
st.update_Query(gra.flatt, In, v)
st.update_Query(gra.flatt, Out, v*-1)
gra.flatt[In]=v
gra.flatt[Out]=(v*-1)
ZnJvbSBtYXRoIGltcG9ydCBjZWlsLGxvZwpkZWYgYmlucG93KGEsYik6CiAgICByZXM9MQogICAgd2hpbGUgYiA+IDAgOgogICAgICAgIGlmIGIgJiAxIDpyZXMgPSByZXMgKiBhCiAgICAgICAgYSAqPSBhCiAgICAgICAgYiA+Pj0gMQogICAgcmV0dXJuIHJlcwoKY2xhc3MgU1RyZWU6CiAgICBkZWYgX19pbml0X18oc2VsZixhcnIpOgogICAgICAgIHNlbGYuYXJyX3NpemUgPSBsZW4oYXJyKS0xCiAgICAgICAgaGVpZ2h0PWNlaWwobG9nKHNlbGYuYXJyX3NpemUrMSwyKSkKICAgICAgICBTVF9zaXplID0gKCAyICogYmlucG93KDIsaGVpZ2h0KSApIC0gMQogICAgICAgIHNlbGYuU1Q9W05vbmUgZm9yIF8gaW4gcmFuZ2UoU1Rfc2l6ZSldCiAgICAgICAgc2VsZi5idWlsZF9TVChhcnIsIDAsIDAsIHNlbGYuYXJyX3NpemUpCgogICAgCiAgICBkZWYgYnVpbGRfU1Qoc2VsZixhcnIsaW5kLEwsUik6CiAgICAgICAgaWYgTCA9PSBSOgogICAgICAgICAgICBzZWxmLlNUW2luZF0gPSBhcnJbTF0KICAgICAgICAgICAgcmV0dXJuIHNlbGYuU1RbaW5kXQogICAgICAgIG1pZCA9IEwgKyAoUiAtIEwpLy8yCiAgICAgICAgc2VsZi5TVFtpbmRdPXNlbGYuYnVpbGRfU1QoYXJyLCBpbmQqMisxLCBMLCBtaWQpK3NlbGYuYnVpbGRfU1QoYXJyLCBpbmQqMisyLCBtaWQrMSwgUikKICAgICAgICByZXR1cm4gc2VsZi5TVFtpbmRdCgogICAgZGVmIHNlYXJjaF9RdWVyeShzZWxmLEwsUik6CiAgICAgICAgaWYgTCA+IFIgb3IgTCA8IDAgb3IgUiA+IHNlbGYuYXJyX3NpemU6CiAgICAgICAgICAgIHJldHVybiBOb25lCiAgICAgICAgcmV0dXJuIHNlbGYuc2VhcmNoX0hlbHAoIDAsIDAsIHNlbGYuYXJyX3NpemUsIEwsIFIpCiAgICAKICAgIGRlZiBzZWFyY2hfSGVscChzZWxmLCBpbmQsIHN0YXJ0LCBlbmQsIEwsIFIpOgogICAgICAgIGlmIEwgPD0gc3RhcnQgYW5kIFIgPj0gZW5kOgogICAgICAgICAgICByZXR1cm4gc2VsZi5TVFtpbmRdCiAgICAgICAgaWYgZW5kIDwgTCBvciBzdGFydCA+IFI6CiAgICAgICAgICAgIHJldHVybiAwCiAgICAgICAgbWlkPShzdGFydCsoZW5kLXN0YXJ0KS8vMikKICAgICAgICByZXR1cm4gc2VsZi5zZWFyY2hfSGVscCgyKmluZCsxLHN0YXJ0LG1pZCxMLFIpK3NlbGYuc2VhcmNoX0hlbHAoMippbmQrMixtaWQrMSxlbmQsTCxSKQogICAgCiAgICBkZWYgdXBkYXRlX1F1ZXJ5KHNlbGYsIGFyciwgaW5kLCB2YWwpOgogICAgICAgIGlmIGluZCA8IDAgb3IgaW5kID4gc2VsZi5hcnJfc2l6ZToKICAgICAgICAgICAgcmV0dXJuIE5vbmUKICAgICAgICBkaWZmPXZhbC1hcnJbaW5kXQogICAgICAgIGFycltpbmRdPXZhbAogICAgICAgIHNlbGYuaGVscF9VcGRhdGUoIDAsIHNlbGYuYXJyX3NpemUsIGluZCwgZGlmZiwwKQogICAgCiAgICBkZWYgaGVscF9VcGRhdGUoc2VsZiwgc3RhcnQsIGVuZCwgdXBkYXRlX2luZCwgZGlmZiwgY3Vycl9pbmQpOgogICAgICAgIGlmIHVwZGF0ZV9pbmQgPCBzdGFydCBvciB1cGRhdGVfaW5kID4gZW5kOgogICAgICAgICAgICByZXR1cm4KICAgICAgICBzZWxmLlNUW2N1cnJfaW5kXSArPSBkaWZmCiAgICAgICAgaWYgc3RhcnQgIT0gZW5kOgogICAgICAgICAgICBtaWQgPSBzdGFydCArIChlbmQtc3RhcnQpLy8yCiAgICAgICAgICAgIHNlbGYuaGVscF9VcGRhdGUoc3RhcnQsIG1pZCwgdXBkYXRlX2luZCwgZGlmZiwgY3Vycl9pbmQqMiArMSkKICAgICAgICAgICAgc2VsZi5oZWxwX1VwZGF0ZShtaWQrMSwgZW5kLCB1cGRhdGVfaW5kLCBkaWZmLCBjdXJyX2luZCoyICsyKQogICAgICAgICAgICAKY2xhc3MgR3JhcGg6CiAgICBkZWYgX19pbml0X18oc2VsZixWKToKICAgICAgICBzZWxmLlY9VgogICAgICAgIHNlbGYuZ3JhcGg9W1tdIGZvciBpIGluIHJhbmdlKFYrMSldCiAgICAgICAgc2VsZi5WaXNpdGVkPXNldCgpCiAgICAgICAgc2VsZi5jb3VudD0wCiAgICAgICAgc2VsZi5pbnRpbWU9ZGljdCgpCiAgICAgICAgc2VsZi5vdXR0aW1lPWRpY3QoKQogICAgICAgIAogICAgZGVmIGFkZEVkZ2VzKHNlbGYpOgogICAgICAgIHNlbGYud2VpZ2h0PVtpbnQoeCkgZm9yIHggaW4gaW5wdXQoKS5zcGxpdCgpXQogICAgICAgIGZvciBfIGluIHJhbmdlKGxlbihzZWxmLmdyYXBoKS0yKToKICAgICAgICAgICAgdSx2PW1hcChpbnQsIGlucHV0KCkuc3BsaXQoKSkKICAgICAgICAgICAgc2VsZi5ncmFwaFt1XS5hcHBlbmQodikKICAgICAgICAgICAgc2VsZi5ncmFwaFt2XS5hcHBlbmQodSkKICAgICAgICAgICAgCiAgICBkZWYgREZTKHNlbGYsTm9kZSk6CiAgICAgICAgc2VsZi5pbnRpbWVbTm9kZV09c2VsZi5jb3VudAogICAgICAgIHNlbGYuY291bnQrPTEKICAgICAgICBzZWxmLlZpc2l0ZWQuYWRkKE5vZGUpCiAgICAgICAgZm9yIGVhY2ggaW4gc2VsZi5ncmFwaFtOb2RlXToKICAgICAgICAgICAgaWYgZWFjaCBub3QgaW4gc2VsZi5WaXNpdGVkOgogICAgICAgICAgICAgICAgc2VsZi5ERlMoZWFjaCkKICAgICAgICBzZWxmLm91dHRpbWVbTm9kZV09c2VsZi5jb3VudAogICAgICAgIHNlbGYuY291bnQrPTEKICAgIAogICAgZGVmIGNvbnN0cnVjdEZsYXR0KHNlbGYpOgogICAgICAgIHNlbGYuZmxhdHQ9WzAgZm9yIGkgaW4gcmFuZ2Uoc2VsZi5WKjIpXQogICAgICAgIGZvciBpIGluIHJhbmdlKDEsc2VsZi5WKzEpOgogICAgICAgICAgICBzZWxmLmZsYXR0W3NlbGYuaW50aW1lW2ldXT1zZWxmLndlaWdodFtpLTFdCiAgICAgICAgICAgIHNlbGYuZmxhdHRbc2VsZi5vdXR0aW1lW2ldXT0oc2VsZi53ZWlnaHRbaS0xXSotMSkKICAgICAgICAgICAgClYsIFEgPSBtYXAoaW50LGlucHV0KCkuc3BsaXQoKSkKZ3JhID0gR3JhcGgoVikKZ3JhLmFkZEVkZ2VzKCkKZ3JhLkRGUygxKQpncmEuY29uc3RydWN0RmxhdHQoKQpzdCA9IFNUcmVlKGdyYS5mbGF0dCkKZm9yIF8gaW4gcmFuZ2UoUSk6CiAgICB0eSwgdSwgdiA9IG1hcChpbnQsIGlucHV0KCkuc3BsaXQoKSkKICAgIGlmIHR5ID09IDE6CiAgICAgICAgdV9JbiA9IGdyYS5pbnRpbWVbdV0KICAgICAgICB1X091dCA9IGdyYS5vdXR0aW1lW3VdCiAgICAgICAgdl9Jbj1ncmEuaW50aW1lW3ZdCiAgICAgICAgdl9PdXQ9Z3JhLm91dHRpbWVbdl0KICAgICAgICBpZiAodV9JbiA8PSB2X0luIDw9IHVfT3V0KSBvciAodl9JbiA8PSB1X0luIDw9IHZfT3V0KToKICAgICAgICAgICAgaWYgdV9JbiA8PSB2X0luOgogICAgICAgICAgICAgICAgcHJpbnQoc3Quc2VhcmNoX1F1ZXJ5KHVfSW4sIHZfSW4pKQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgcHJpbnQoc3Quc2VhcmNoX1F1ZXJ5KHZfSW4sIHVfSW4pKQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIHByaW50KC0xKQogICAgZWxzZToKICAgICAgICBJbj1ncmEuaW50aW1lW3VdCiAgICAgICAgT3V0PWdyYS5vdXR0aW1lW3VdCiAgICAgICAgc3QudXBkYXRlX1F1ZXJ5KGdyYS5mbGF0dCwgSW4sIHYpCiAgICAgICAgc3QudXBkYXRlX1F1ZXJ5KGdyYS5mbGF0dCwgT3V0LCB2Ki0xKQogICAgICAgIGdyYS5mbGF0dFtJbl09dgogICAgICAgIGdyYS5mbGF0dFtPdXRdPSh2Ki0xKQo=