Here is a link to the problem.

Briefly, there is a tree with some values on each node. For each query a,b, I have to find the contiguous subarray with maximum sum in the path a — b. There are range updates a b v, which change the value of the nodes in a — b to some v.

My approach is to decompose the tree (heavy light) and then find the answer(I'll come to what I mean by this) for a -> lca(a,b), and then the same for b -> lca(a,b).

If the path from a -> lca(a,b) passes through five chains, I get all the answers for each chain in the range that belongs to the path a -> lca(a,b). The answer consists of max sum, max prefix sum, max postfix sum, total sum. I store these in a list. And do the same for b -> lca(a,b). I concatenate the two lists appropriately. Then on this final list, I calculate the final answer (exactly same as what's been done for the segment trees of the chains).

Is there a better way that doesn't involve joining all the answers of the involved chains and then finding the answer from them? I'll explain more if I needed.