### I_love_Vovuh_s_cat's blog

By I_love_Vovuh_s_cat, history, 10 months ago, ,

Given a tree with n nodes, rooted at 1. You have q offline queries with the form of ui, vi and xi. You have to add xi to every node in the simple path from ui to vi. It is guaranteed than ui is an ancestor of vi. Then you have to print out the values of all the nodes. The limit is... well, too large for O(n^2). Could anyone give me an approach to this problem?

• +3

 » 10 months ago, # | ← Rev. 4 →   0 Since you asked for an approach, I won't go in details, but just give the approach.Edit: Seems like I've overkilled it for both online and offline. Refer to ulna's solution for the simple approach. For O(log) amortized time for a query you can use centroid decomposition. Each time you find the centroid you can process all queries that pass through it in constant amortized time per query.Additionally, in case you want to solve the problem online, there's a O(log2) per query solution using heavy-light decomposition with lazy-propagation segment trees for the heavy paths.
•  » » 10 months ago, # ^ |   0 Thank you for your help. The term sounds very new, but i will try my best to understand it.
•  » » 10 months ago, # ^ |   0 I didn't quite understand how to process queries on centroid tree (let's say we already built it). Can you elaborate more?
•  » » » 10 months ago, # ^ |   0 Boils down to pretty much ulna's solution but even slightly simpler. However since that solution will work for the whole problem, doing centroid decomposition is an overkill.
•  » » » » 10 months ago, # ^ |   0 I still couldn't think of a centroid decomposition approach for this problem but there is a heavy-light decomposition approach, which is pretty much straight forward like ulna's trick but for log(n) arrays.
 » 10 months ago, # |   +25 Another approach is to use partial sum on tree. SpoilerFor every query(u, v, x), add x to v and  - x to parent(u).Then run a dfs in root, add all children's value of every node.Like: query(u, v, x) d[v] += x d[parent(u)] -= x dfs(v) for every child u of v dfs(u) d[v] += d[u] d would be the answer array.
•  » » 10 months ago, # ^ |   0 Thank you for your help. This sounds simpler but i will try to be able to implement both.
 » 10 months ago, # |   +3 https://codeforces.com/contest/1076/problem/ESimilar problem if you want to try another one.