fork download
copy 
  1. from math import ceil,log
  2. def binpow(a,b):
  3.     res=1
  4.     while b > 0 :
  5.         if b & 1 :res = res * a
  6.         a *= a
  7.         b >>= 1
  8.     return res
  9.  
  10. class STree:
  11.     def __init__(self,arr):
  12.         self.arr_size = len(arr)-1
  13.         height=ceil(log(self.arr_size+1,2))
  14.         ST_size = ( 2 * binpow(2,height) ) - 1
  15.         self.ST=[None for _ in range(ST_size)]
  16.         self.build_ST(arr, 0, 0, self.arr_size)
  17.  
  18.  
  19.     def build_ST(self,arr,ind,L,R):
  20.         if L == R:
  21.             self.ST[ind] = arr[L]
  22.             return self.ST[ind]
  23.         mid = L + (R - L)//2
  24.         self.ST[ind]=self.build_ST(arr, ind*2+1, L, mid)+self.build_ST(arr, ind*2+2, mid+1, R)
  25.         return self.ST[ind]
  26.  
  27.     def search_Query(self,L,R):
  28.         if L > R or L < 0 or R > self.arr_size:
  29.             return None
  30.         return self.search_Help( 0, 0, self.arr_size, L, R)
  31.  
  32.     def search_Help(self, ind, start, end, L, R):
  33.         if L <= start and R >= end:
  34.             return self.ST[ind]
  35.         if end < L or start > R:
  36.             return 0
  37.         mid=(start+(end-start)//2)
  38.         return self.search_Help(2*ind+1,start,mid,L,R)+self.search_Help(2*ind+2,mid+1,end,L,R)
  39.  
  40.     def update_Query(self, arr, ind, val):
  41.         if ind < 0 or ind > self.arr_size:
  42.             return None
  43.         diff=val-arr[ind]
  44.         arr[ind]=val
  45.         self.help_Update( 0, self.arr_size, ind, diff,0)
  46.  
  47.     def help_Update(self, start, end, update_ind, diff, curr_ind):
  48.         if update_ind < start or update_ind > end:
  49.             return
  50.         self.ST[curr_ind] += diff
  51.         if start != end:
  52.             mid = start + (end-start)//2
  53.             self.help_Update(start, mid, update_ind, diff, curr_ind*2 +1)
  54.             self.help_Update(mid+1, end, update_ind, diff, curr_ind*2 +2)
  55.  
  56. class Graph:
  57.     def __init__(self,V):
  58.         self.V=V
  59.         self.graph=[[] for i in range(V+1)]
  60.         self.Visited=set()
  61.         self.count=0
  62.         self.intime=dict()
  63.         self.outtime=dict()
  64.  
  65.     def addEdges(self):
  66.         self.weight=[int(x) for x in input().split()]
  67.         for _ in range(len(self.graph)-2):
  68.             u,v=map(int, input().split())
  69.             self.graph[u].append(v)
  70.             self.graph[v].append(u)
  71.  
  72.     def DFS(self,Node):
  73.         self.intime[Node]=self.count
  74.         self.count+=1
  75.         self.Visited.add(Node)
  76.         for each in self.graph[Node]:
  77.             if each not in self.Visited:
  78.                 self.DFS(each)
  79.         self.outtime[Node]=self.count
  80.         self.count+=1
  81.  
  82.     def constructFlatt(self):
  83.         self.flatt=[0 for i in range(self.V*2)]
  84.         for i in range(1,self.V+1):
  85.             self.flatt[self.intime[i]]=self.weight[i-1]
  86.             self.flatt[self.outtime[i]]=(self.weight[i-1]*-1)
  87.  
  88. V, Q = map(int,input().split())
  89. gra = Graph(V)
  90. gra.addEdges()
  91. gra.DFS(1)
  92. gra.constructFlatt()
  93. st = STree(gra.flatt)
  94. for _ in range(Q):
  95.     ty, u, v = map(int, input().split())
  96.     if ty == 1:
  97.         u_In = gra.intime[u]
  98.         u_Out = gra.outtime[u]
  99.         v_In=gra.intime[v]
  100.         v_Out=gra.outtime[v]
  101.         if (u_In <= v_In <= u_Out) or (v_In <= u_In <= v_Out):
  102.             if u_In <= v_In:
  103.                 print(st.search_Query(u_In, v_In))
  104.             else:
  105.                 print(st.search_Query(v_In, u_In))
  106.         else:
  107.             print(-1)
  108.     else:
  109.         In=gra.intime[u]
  110.         Out=gra.outtime[u]
  111.         st.update_Query(gra.flatt, In, v)
  112.         st.update_Query(gra.flatt, Out, v*-1)
  113.         gra.flatt[In]=v
  114.         gra.flatt[Out]=(v*-1)
  115.  
Success #stdin #stdout 0.02s 9296KB
comments (?)
stdin
copy 
3 5
1 2 3
1 2
1 3
2 3 6
2 2 4
1 1 2
1 2 3
1 1 3
stdout
copy 
5
-1
7
https://ideone.com/QWCK3m
language:
Python 3 (python  3.12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!