Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### rhezo's blog

By rhezo, history, 7 years ago,

How to solve this problem?

Statement: Given N nodes of a tree, answer Q queries of 2 types(update value of some node or find the number of distinct numbers on the path from U to V).

There is a solution with Mo's algorithm with updates and I don't understand that as well. Can anyone explain any other approach or even this one?

• +10

 » 7 years ago, # |   0 Auto comment: topic has been updated by rhezo (previous revision, new revision, compare).
 » 7 years ago, # |   +15 Update query on Mo Mo on trees Maybe these links can help you.
 » 7 years ago, # | ← Rev. 2 →   +23 Perform a DFS of the tree and obtain the dfs start and end times , if a query is from to , let . Assume . If then query is from to else query is from to along with . You need the frequency of elements from this range whos nodes appear exactly once in the range , to do that , break the array into blocks , and for each pair of blocks , calculate the frequency table ans the answer for that block. Now each query can be brocken in to a prefix + a pair of block + a suffix. The size of the prefix and suffix is atmost So add those elements by brute. To do an update traverse each pair once and update the frequency table accordingly. Total Complexity .
•  » » 7 years ago, # ^ |   0 The problem is almost the same as this problem, and can be solved with the same complexity in a manner very similar to Mo's algorithm by sorting the queries via , where starting and ending blocks are the blocks which the first and last elements of the query belong to, respectively. Code for this problem: Link.
•  » » » 7 years ago, # ^ |   0 I understood the entire logic from your code but I have one doubt about the update queries. If the queries are given in this order : RQ1, RQ2, UP1, UP2, UP3, UP4, RQ3, RQ4(RQ is a range query and UP is an update query).When the range queries are sorted if the order we get is :RQ3, RQ1, RQ4, RQ2, then all the update queries will be processed for every range query. This would lead to O(Q^2).Please correct me if I am wrong.
•  » » » » 7 years ago, # ^ |   +1 All range queries are sorted according to the tuple: ( meaning first sort by starting block, then by ending block, and finally by time of query. ) Notice that the number of distinct values of the tuple are N2 / 3, and all Range Queries with the same value of will be sorted in the increasing order of time of query. The Q updates need to be processed only once for this group of queries. Hence total number of times we need to perform update is: Q * N2 / 3 , not Q2 . You can refer code to see how to perform these updates.
•  » » » » » 7 years ago, # ^ |   +1 Very nice explanation. Thanks a lot!
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I saw your solution and understood everything! Thanks a lot :)
 » 7 years ago, # |   +11 Hey.Can anyone give me a link to a problem which is solvable with Mo's algoritm on array with updates? I'd like to practice this method.
•  » » 7 years ago, # ^ |   +1