Hello everyone.

Recent codechef long challenge had a task about queries on paths inside a tree: short, given a tree, each vertex contains a linear function, and given $$$q$$$ queries of types "add given linear $$$f$$$ to all vertices of the path between $$$u$$$ and $$$v$$$" and "calculate maximum of $$$f(z)$$$ where $$$z$$$ is given and $$$f$$$ is a function in any of vertices on the path between given $$$u$$$ and $$$v$$$", $$$n$$$ and $$$q$$$ are $$$\leq 10^5$$$, time limit is 4s.

It seems that the intended time complexity is $$$O(n\sqrt{n}\log{n})$$$, but I heard that it required efforts to get AC with this solution. On the other hand, it's easy to get ac with an $$$O(nq)$$$ solution.

Don't get it wrong: if we iterate over a path just, for example, by going from both endpoints towards the root, it gets tl (even with pragmas): submission. On the other hand, one can use heavy-light decomposition (this particular implementation is not necessary, I suppose, but it's still very nice) first (that is, sort every vertex' children by their subtree sizes), then rearrange vertices by their dfs in-order, and voilà, every path is now a union of about $$$\sim\log{n}$$$ consecutive segments. If we now do basically the same stupid implementation of what we are asked for in the statement, we get ac for 1.6s with pragmas and even ac for 2.6s without pragmas.

Hope this trick is not a mutual knowledge (though it's definitely not a common knowledge). I found it so simple and potentially usable that it deserves a post in my opinion.