We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
fromcollectionsimportdefaultdict,dequeimportsysdefread():return(int(s)forsinsys.stdin.readline().split())N,Q=read()adj_matrix=defaultdict(list)for_inrange(N-1):x,y=read()adj_matrix[x].append(y)adj_matrix[y].append(x)segment_size=120parents=[None]*Ns_parent=[None]*Ns_weight=[0]*Nlevels=[0]*Nupdate=[-1]*Nrefresh=[-1]*Nweight=[0]*Ndefrefresh_segment(node,sp,tick):ifnode==sporrefresh[node]>=update[sp]:returnparent=parents[node]ifparent==sp:s_weight[node]=weight[parent]else:refresh_segment(parent,sp,tick)s_weight[node]=s_weight[parent]+weight[parent]refresh[node]=tick# Initialize above with BFS, que is (segment parent, parent, node, level)que=deque([(0,0,0,0)])whileque:segment,parent,node,level=que.popleft()s_parent[node]=segmentparents[node]=parentlevels[node]=levelchild_segment=segmentiflevel%segment_sizeelsenodeforninadj_matrix[node]:ifn!=parent:que.append((child_segment,node,n,level+1))results=[]foriinrange(Q):op,u,x=read()ifop==1:weight[u]=xiflevels[u]%segment_size:update[s_parent[u]]=ielse:update[u]=ielse:iflevels[u]>levels[x]:u,x=x,uresult=weight[x]+weight[u]# Traverse x upwards segment by segment until# levels[segments[x]] == levels[segments[u]]u_s=s_parent[u]whilelevels[s_parent[x]]>levels[u_s]:refresh_segment(x,s_parent[x],i)result+=s_weight[x]x=s_parent[x]whiles_parent[x]!=s_parent[u]:refresh_segment(x,s_parent[x],i)refresh_segment(u,s_parent[u],i)result+=s_weight[x]result+=s_weight[u]x=s_parent[x]u=s_parent[u]for_inrange(levels[x]-levels[u]):x=parents[x]result+=weight[x]whileu!=x:x=parents[x]u=parents[u]result+=weight[x]result+=weight[u]result-=weight[x]results.append(result)print('\n'.join(str(x)forxinresults))
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Lazy White Falcon
You are viewing a single comment's thread. Return to all comments →
PyPy 3 solution