I have been recently doing this problem: https://codebreaker.xyz/problem/truck . Please read it before reading my question.

I have written code for it which has a time complexity of O(nlogn + q * logn) which should be sufficient to solve the question. Also, my code passes the two example testcases given in the problem statement. However, when I submit my code, it fails EVERY SINGLE other testcase. I have been debugging my code for almost a week now, trying to see if I am getting integer overflow anywhere, or if my logic is wrong. But i simply haven't found anything. I am asking you guys, PLEASE, for the sake of my sanity, help me solve my problem.

My code: https://pastebin.com/fnWh1Xbc

Definitions: Even though tolls are assigned to edges, I'm going to assign nodes tolls instead. Namely, the toll of a node is the toll of the edge from its parent, to itself. Also, total distance of some node a is the distance from the root to a. Total toll of some node a is the sum of tolls from the path from the root to a.

My main piece of logic: Consider wanting to find out the fuel needed to go from the root to some node, a. This is just equal to going from the root to the parent of a + (toll of a * total distance of parent of a) because adding the node a to the end of the path from the root to parent of a increases the toll you have to carry from root to parent of a by the toll of a. So in my fenwick tree, called to_node, I update the in time of node a to this value (toll of a * distance from root to parent of a) and the out time of node a to negative of this value. This is so that only nodes in the subtree of node a should get added with this value when wanting to find out fuel needed to go to root. So to calculate fuel needed to go from some node a, to root, it is just equal to from_node.sum(in_out[a].first). Now consider wanting to go from some node a to root. Notice that for every node x you reach in the path from a to root, you have to hold toll of x less gold bars in the path from x to root. So the total fuel saved by paying the toll of x at x is = total distance of x * toll of x. Therefore, to the fenwick tree, called from_node, at the in time of x i change the value to this (total distance of x * toll of x) and at the out time of x i change the value to the negative of this value for the same reason above. Then to calculate going from some node a, to root, it is just total toll of a * total distance of a — to_node.sum(in_out[a].first). (sorry if i didn't explain this bit very well. I learned this idea from another similar question i have done before.) Namely, this one: https://codebreaker.xyz/problem/dragonfly

Note; to_root and from_root functions are explained above. And so are all the update functions so I won't explain them again.

explanation of my code: I first do a dfs call (called calculate_city_info in my code) to calculate the depth, in_out time, distance from root of each city, as well as create the euler tour for finding LCA. I also update total_toll, from_node, and to_node at each node in the way described above. Next, for each query operation, I first find the LCA of the start and end. So first, i calculate going from the start to the LCA. This is equal to to_root(start) — to_root(LCA) — total toll of LCA * distance to LCA. I have to minus the additional (total toll of LCA * distance to LCA) because I carry the total toll of LCA gold bars extra in the path from start to LCA. However, I also have to add (distance to LCA * total toll from LCA to end) because that is how much more gold bars I have to carry in order to have enough to go from the LCA to the end and i have to carry it from the start to LCA. Next, I need to calculate fuel needed to go from the LCA to the end. This would be equal to from_root(end) — from_root(LCA) but I have to minus an additional (total toll from LCA to end * total distance of LCA) Because I carry more gold bars from the start when i'm going to the end vs when I'm only going to LCA. So now, I just have to add these two values. But wait, I haven't even taken into account for g yet. But this is quite simple, For the whole distance from the start to end, I just have to carry g extra gold bars. So i just add (distance from start to end * g). And when I add up all these values, I get my answer. I also have modded my values everywhere I can in order to stop integer overflow.

Also, all update operations just involve me updating the to_node, from_node, and total_toll in the same way that I did for dfs for the node with higher depth.

So what is wrong with my code or with my logic? I would be eternally debted to you if you can help me. Thanks!