Alternate approach with same time complexity using Mo’s algorithm.
The idea is similar to : FCTRE - Editorial
Implementation : CodeChef: Practical coding for everyone
Idea:
- We can flatten the tree with euler tour and then use Mo’s algorithm to answer the queries.
- Each query L,R will be converted to end(L),start(R) where end(L) denotes the last occurrence of node L and start(R) denotes the first occurence of R.
- We maintain the scalar product when we traverse queries using Mo’s algorithm and we will get scalar product for nodes in path from node L to node R excluding the LCA(L,R).
- Remember, if a node appears twice in the given range of euler tour, we will remove it. For understanding better refer to FCTRE - Editorial
- We precompute the sum of squares (SOS) of value from root to each node and add SOS[LCA(L,R)] to each query’s answer.