Notes 1: AtCoder ABC 133F
Difference between en18 and en19, changed 2 character(s)
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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en30 English NeoYL 2023-12-31 12:37:32 7
en29 English NeoYL 2023-12-14 19:34:13 18
en28 English NeoYL 2023-12-14 19:32:15 348
en27 English NeoYL 2023-12-14 19:26:45 17 Tiny change: '\n<spoiler> \n```cpp' -> '\n<spoiler summary="Code"> \n```cpp'
en26 English NeoYL 2023-12-14 19:26:18 5298
en25 English NeoYL 2023-12-14 17:59:14 5 Tiny change: 'timization">\nWe can' -> 'timization used">\nWe can'
en24 English NeoYL 2023-12-14 13:29:32 12 Tiny change: ' summary="Half solution"' -> ' summary="Incomplete solution"'
en23 English NeoYL 2023-12-14 08:58:57 215
en22 English NeoYL 2023-12-14 08:57:58 141 Tiny change: ' summary="$O(N^2)$ s' -> ' summary=" $O(N^2)$ s'
en21 English NeoYL 2023-12-13 13:27:55 15
en20 English NeoYL 2023-12-12 13:33:13 4
en19 English NeoYL 2023-12-12 09:13:23 2 Tiny change: 'ed to add +1 to each n' -> 'ed to add $+1$ to each n'
en18 English NeoYL 2023-12-12 05:48:22 2 Tiny change: 'round 2400 ish proble' -> 'round 2400-ish proble'
en17 English NeoYL 2023-12-12 04:44:37 8
en16 English NeoYL 2023-12-12 03:55:24 86
en15 English NeoYL 2023-12-12 03:47:05 36 Tiny change: 'n problems, which ar' -> 'n problems (normally around 2300 ish problems), which ar'
en14 English NeoYL 2023-12-12 03:46:04 16
en13 English NeoYL 2023-12-12 03:45:29 20 Tiny change: 'note 2), an upvote would be ' -> 'note 2), a significant upvote from you would be '
en12 English NeoYL 2023-12-12 03:42:52 160
en11 English NeoYL 2023-12-12 03:38:43 22
en10 English NeoYL 2023-12-12 03:37:41 324
en9 English NeoYL 2023-12-11 19:35:45 4 Tiny change: 'at a point $p$. What do ' -> 'at a point. What do '
en8 English NeoYL 2023-12-11 19:34:44 19 Tiny change: 'e able to continue from here' -> 'e able to solve the problem from here'
en7 English NeoYL 2023-12-11 19:27:44 64
en6 English NeoYL 2023-12-11 19:26:56 40 Tiny change: 'e set.\n\n[AC co' -> 'e set.\n\nThis allows an $O(N log N)$ solution\n\n[AC co'
en5 English NeoYL 2023-12-11 19:26:07 20 Tiny change: 'n the path.\n\nNow' -> 'n the path * new weight length.\n\nNow'
en4 English NeoYL 2023-12-11 19:25:11 262
en3 English NeoYL 2023-12-11 19:23:21 8421 (published)
en2 English NeoYL 2023-12-11 19:07:37 7364
en1 English NeoYL 2023-12-11 19:00:00 1500 Initial revision (saved to drafts)