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 (normally around 2400-ish problems), which are completely solved by myself without looking at the editorial, that are both interesting and educational. If you want to motivate me to write a continuation (aka note 2), a significant upvote from you would be well appreciated! ↵
↵
Problem link: [ABC133F](https://atcoder.jp/contests/abc133/tasks/abc133_f)↵
↵
Try to solve the task independently before continuing the blog.↵
↵
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)↵
↵
Feel free to ask anything about the task. I will try to respond them if I am free.
↵
Problem link: [ABC133F](https://atcoder.jp/contests/abc133/tasks/abc133_f)↵
↵
Try to solve the task independently before continuing the blog.↵
↵
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)↵
↵
Feel free to ask anything about the task. I will try to respond them if I am free.
