Auto comment: topic has been updated by misterPerfect (previous revision, new revision, compare).

Auto comment: topic has been updated by misterPerfect (previous revision, new revision, compare).

Auto comment: topic has been updated by misterPerfect (previous revision, new revision, compare).

You could share your code, I can identify optimizations. I primarily code in java and python. I solved many cses in those languages.

Hey! I saw your code, eventhough it is asymtotically optimal, there are few optimizations you could do. 1. You are accumulating ranges in a vector and querying the segment tree later. Instead directly query the segment tree. Avoid the intermediate list overhead. 2. This is not needed:
if (par != -1) { node.leg.erase(find(node.leg.begin(), node.leg.end(), par)); node.depth = 1 + T[par].depth; } 3. Try doing minor optimizations here and there.

For each node v, call value[v] as the value assigned to the node and sum[v] as the sum from root of the tree to that node v.

For each node v, we will store sum[v] in its euler tour location.

Incrementing the value of node v by x, increases root to node sum values for all the nodes in the subtree of v by x. Since subtrees correspond to subarrays, this is an equivalent range increment operation on an array.

Finding the sum of values on a u-v path is equal to sum[u] + sum[v] — 2*sum[lca] + value[lca]. sum[u], sum[v], sum[lca] are all just values in the euler tour array.

So effectively, we need to support two operations on the euler tour array: 1. Performing Range increment on an subarray. 2. Querying value at index on an array.

Both of these operations can be simultaneously supported by either a binary indexed tree or a segment tree. (with segment tree you'll need to implement lazy prop, but with BIT its far simpler).