Sounds like you might be leaving the path in the middle all the times but you enter a path in the middle at most once. Can't prefix sums help you then?

Yeah, in order to have an solution using HLD, we'd need a "dynamic prefix sums" structure with O(1) complexities of query and update.

I think that a possible o((N+Q+M) log N) solution (Q = queries, M = modifications, N = number of vertices of the tree) may be the following:

You have at most log N heavy paths. So you can store for each heavy edge E, the heavy paths H(E) such that if you are standing at the root of any of the H(E) heavy paths and you want to go to the root you have to traverse the edge E. Then whenever you update an edge in the heavy path that contains E and in E or a closer to the root edge, you also make the update in all the H(E) heavy paths.

Let's define H in a more formal way. If A-B is an edge, and A is closer to the root than B, then we associate B with that edge (as B has only one parent but A may have more than one child). Let's call that edge E[B]. If E[B] is heavy then there exists a heavy path that uses A-B. Let's say that the path is for example X-Y-A-B-C-D. Then we use a BIT to store the values of the edges X-Y, Y-A, A-B, B-C and C-D. We also add an edge R-X (R for root), and we store that value outside the BIT. R-X will be the path from X to the root only considering the weights of the heavy edges (that is, the weight of the path to the root if we modify the light edges to have weight 0).

Now we calculate H as follows: We enumerate the BITs that store the heavy paths as follows: Heavy[0], Heavy[1], Heavy[2], ... and for each node T we store in H the indexes of the BITs that correspond to the heavy paths that are below T. We can do it recursively as follows (it's pseudocode, not code):

void fillH(int node)
{
    for(int i=0;i<numberOfHeavyPaths;i++)
    H[node][i] = false;
    for each childe T of node
        fillH(T)
        for(int i=0;i<numberOfHeavyPaths;i++)
            if(H[T][i] == true)
                H[node][i] = true;
            if(E[T] is light && T is the root of Heavy[i])
                H[node][i] = true;
}

And we call fillH(root).

Then we ignore H for the light edges. Now we must fill the R-X edge for each BIT. We can do it as follows:

void updatePathToTheRoot(int BITnumber)
{
    RX[BITNumber] = 0;
    for(int i=0;i<N;i++)
    if(E[i] is heavy and H[i][BITNumber] == true)
        RX[BITNumber] += weight(E[i]);
}

and we call this for each 0 <= BITNumber < NumberOfHeavyPaths

Then every time we make an update to a heavy edge, we search for the heavy paths that are below that edge and update that value as follows:

void update(int node, int newWeight) //remember we asociated each edge with the child in that edge
{
    int BITNumber = getBITNumber(node);// we can precalculate for each heavy edge, to which path it belongs
    updateBIT(BITNumber,node,newWeight);
    for(int i=0;i<numberOfHeavyPaths;i++)
    if(H[node][i] == true)
        RX[i] += newWeight-oldWeight;
}

and now the query is just asking for the light edges, for the first heavy path, and for the RX edge of that path.

I hope you all understand this solution, if needed I can write code and post it here.

I know this post is about heavy-light, but this problem looks a lot easier to solve without it.

When you change edge from x to x's parent and increase it by d, what you are doing is increasing "distance to root" by d for every vertex in x's subtree. So you can keep the distances to root in pre-order, and update them using a BIT.

The link-cut tree paper ("A Data Structure for Dynamic Trees", Sleator and Tarjan 1982) uses biased binary search trees to get from down to . The same concept can be aplied to the special case of a static heavy-light decomposition, using static binary search trees.

you can try divide and conquer and for query(left,right) build virtual tree with node in this intervals..

it is O(Q*log(Q))..