This is my personal note and might be some kind of user editorial/learning material for some people. This is the first episode of this "note series". I will write notes on problems that are interesting and educational. If you want to help/motivate me to write a continuation, an upvote would be nice!↵
↵
[ABC133F](https://atcoder.jp/contests/abc133/tasks/abc133_f) :↵
↵
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 solve the problem 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. What do we need to have if we want to do these operations fast? **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↵
↵
[AC code here](https://atcoder.jp/contests/abc133/submissions/48433973)↵
↵
Give me an upvote if you have learned something from this blog as this might motivate me to write more. Thanks in advance!↵
↵
[ABC133F](https://atcoder.jp/contests/abc133/tasks/abc133_f) :↵
↵
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 solve the problem 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. What do we need to have if we want to do these operations fast? **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↵
↵
[AC code here](https://atcoder.jp/contests/abc133/submissions/48433973)↵
↵
