Question: from collections import defaultdict, deque def solve ( edges , values, queries ) : def dfs ( node , parent ) :

from collections import defaultdict, deque
def solve(edges, values, queries):
def dfs(node, parent):
"""DFS to calculate the start and end indices for each subtree in the Euler tour."""
nonlocal timer
start[node]= timer
euler[timer]= node
timer +=1
for child in tree[node]:
if child != parent:
dfs(child, node)
end[node]= timer -1
# Step 1: Build the tree as an adjacency list
tree = defaultdict(list)
for u, v in edges:
tree[u].append(v)
tree[v].append(u)
# Step 2: Perform an Euler tour to map nodes to array indices for subtree updates
N = len(values)
start =[0]*(N +1)
end =[0]*(N +1)
euler =[0]*(N +1)
timer =1
dfs(1,-1) # Assume 1 is the root node
# Step 3: Initialize lazy propagation arrays
subtree_add =[0]*(N +2)
non_subtree_add =[0]*(N +2)
# Step 4: Process each query
for t, x, y in queries:
if t ==1: # Increment the subtree of node x
subtree_add[start[x]]+= y
subtree_add[end[x]+1]-= y
elif t ==2: # Increment everything except the subtree of node x
non_subtree_add[1]+= y
non_subtree_add[N +1]-= y
subtree_add[start[x]]-= y
subtree_add[end[x]+1]+= y
# Step 5: Propagate the lazy updates
# Propagate subtree_add
for i in range(1, N +1):
subtree_add[i]+= subtree_add[i -1]
# Propagate non_subtree_add
for i in range(1, N +1):
non_subtree_add[i]+= non_subtree_add[i -1]
# Step 6: Apply the updates to the original values
result =[0]* N
for i in range(1, N +1):
node = euler[i]
result[node -1]= values[node -1]+ subtree_add[i]+ non_subtree_add[i]
return result
# Input handling
N = int(input())
edges =[list(map(int, input().split())) for _ in range(N -1)]
values = list(map(int, input().split()))
Q = int(input())
queries =[list(map(int, input().split())) for _ in range(Q)]
out_= solve(edges, values, queries)
print(''.join(map(str, out_)))

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!