This is my personal note and might be some kind of user editorial/learning material for some people.
ABC133F :
First of all, we can observe that queries can be done offline and the only thing that matters for each query is the color.
Lets do each color one by one, we can observe that distance between two nodes in the query = original distance $$$-$$$ sum of edge weight of color $$$x$$$ + number of edges that have color $$$x$$$ in the path * new weight length.
Now let us try to find what can be done. We can see that the number of edges with color $$$x$$$ going out of subtree $$$u$$$ will $$$+1$$$ if the starting point is from subtree $$$u$$$. So we can just $$$+1$$$ to all nodes inside subtree $$$u$$$. Then we can see that number of edges from node $$$x$$$ to $$$y$$$. Similarly, we can do $$$+W$$$ for weight sum.
Distance in original graph can be found in $$$O(N log N)$$$ using binary lifting and a dfs function. Simultaneously, since we need to add +1 to each node one by one, we will need to do $$$O(N^2)$$$ to do all necessary operations.
This reduces the problem to $$$O(N ^ 2)$$$, lets optimize it!
We can try finding a better way to do the $$$+1$$$ and $$$+W$$$ operations. Well, if you have learnt dfn, you should be able to continue from here. If we represent $$$tin_{ i }$$$ be the time we entered subtree $$$i$$$ and $$$tout_{ i }$$$ we left subtree $$$i$$$. Then we can use this to observe that we need to do $$$+val$$$ in a range and find a value at a point $$$p$$$. Yes, segment tree!
However, we cannot just declare a new segment tree each time. We need to reuse the segment tree. So, we'll have to do $$$-1$$$ and $$$-W$$$ operations to revert the segment tree, or do something like range set.
This allows an $$$O(N log N)$$$ solution
Give me an upvote if you have learned something from this blog as this might motivate me to write more. Thanks in advance!
