Hello Codeforces ,today I want to introduce a technique that can solve some problems related to distinct values queries on a subtree .The only way I know to solve array distinct values queries with updates is using MO's algorithm .The approach I will introduce can solve the subtree version of this problem online with updates in $$$O((N+Q)log^2(N))$$$.So let's get started.
Prerequisites:
1.Heavy light decomposition (it's enough to know how it works and how to implement it).
2.Lowest common ancestor.
3.Euler tours (not necessary for this specific problem but I will use it to prove some fact).
Problem Statement:
You are given a tree rooted at vertex 1. You have to perform two types of queries:
1 $$$i$$$ $$$val$$$ : update the value of node $$$i$$$ to $$$val$$$.
2 $$$u$$$ : output the sum of distinct values in the subtree of node $$$u$$$.
Solution:
Whenever you encounter such a strange problem try to make a shift in perspective .What is the first thing you thought when you have seen this problem? Euler tour? Persistent Segment trees? Isn't it similar to the array distinct values queries? But wait ,I just said it's hard to solve this problem. Didn't I?
Can we change the problem into path queries problem?
Wait what are the nodes that are affected by an update?
I turns out that the affected nodes are all in a range on the ancestry path of the updated node .Don't it seem like a standard HLD problem?
Not yet .Here comes the idea .Consider our new problem:
We want to update the answers in a range on the ancestry path of a node .So ,where does this range end? If we can figure out how to do this then the problem becomes a standard path update and queries problem that can be easily solved using HLD .Now, here is the fun part.
Isn't it obvious the endpoint is the first node on the ancestry path that doesn't have an occurrence of $$$val$$$?
How can we find such a node? well this is the same as finding the first node on the path that have an occurrence then going down by one edge.
It turns out that this node is the first node that have the closest occurrence of $$$val$$$ in its subtree. But what does it mean for a node to be be the closest?
Well ,let's consider this node to be the $$$lca$$$ of the updated node and the closet node since the $$$lca$$$ is the first node on the ancestry path from the updated node to the root .Now the problem boils down to finding the maximum depth $$$lca$$$ among all possible $$$lca$$$ s ,but how can we do this fast?
Well, if we maintain a map of sets that stores for each number the $$$time in$$$ s in DFS order for the nodes with a value equal to that number then the node we are searching for is the node with maximum depth among $$$lca($$$updated node ,the first node with time in bigger than the $$$time in$$$ of the updated node $$$)$$$ and $$$lca($$$updated node ,the first node with time in smaller than the $$$time in$$$ of the updated node $$$)$$$ .But why is this true in general?
Proof of the above fact:
Let's consider the case of (the first node with time in bigger than the time in of the updated node(let's call this node $$$u$$$)) then the second case will go through an identical reasoning.
Consider taking a node with a bigger time in than $$$u$$$ (let's call it $$$v$$$).
Let $$$x$$$ be the first node on the ancestry path then:
If a node $$$d$$$ is the closest node to $$$i$$$ then $$$d$$$ must be in the subtree of $$$x$$$. Because $$$in[i]<in[u]<in[v]$$$ if $$$v$$$ was in the subtree of $$$x$$$ and $$$i$$$ was in the subtree of $$$x$$$ then also $$$u$$$ is in the subtree of $$$x$$$ .Thus taking $$$u$$$ is at least as optimal as taking node $$$v$$$.
Note : that there is a corner case when there is at least one occurrence of $$$val$$$ in the subtree of $$$i$$$ we don't update anything.
Also note that when we update a node we should remove the old value and add the new value but this is can be done in the same way the adding process is done thus I leave it as an exercise to the reader to check this.
A recap for what we did:
You could reflect on how we transformed a subtree queries problem into a path queries problem which turns out to be much easier if we think that way. Then we used a fact that facilitates using the bruteforce approach by finding optimal values to try .
Implementation:
There are many implementation details that I skipped above but if you are curious here is my code:
I couldn't find any link for a problem that uses this technique so I made one .
link: 521454A - Subtree Distinct Sum Queries
https://codeforces.com/contestInvitation/02c14ae6e9e06b8f0c6a3ce7eb957a1f3ba2f865
Another problem suggested by asdasdqwer :https://dmoj.ca/problem/dmopc20c1p5
You can also optimize heavy light decomposition see https://codeforces.com/blog/entry/104997.
Thank you for reading my blog.
I spent a lot of time preparing this so I hope you loved it.
P.S. This is my first educational blog .Sorry for long text :) .
Edit I said at the beginning of the blog that this is pretty similar to the array distinct values queries task so I will put some resources in case if you want to learn more:
https://codeforces.com/blog/entry/10508?#comment-158835
https://codeforces.com/blog/entry/83630
Thanks to VitalyKo for suggesting the resources .
Auto comment: topic has been updated by Haidora (previous revision, new revision, compare).
Auto comment: topic has been updated by Haidora (previous revision, new revision, compare).
Auto comment: topic has been updated by Haidora (previous revision, new revision, compare).
Actually, there already exists a task which asks for pretty much the same thing: here
In the solution of the task, you can see that it's possible to do in $$$(n+q)log(n)$$$, which is probably better than $$$n*log(n)^2$$$. If you want a hint on how to do it this way, try to think about Euler Tour and LCA only, and don't use HLD. (If you want to solve an easier version of the task first: BOI 2017 — Railway)
First, let's group the nodes in the tree by their color (aka the deputy minister who is suggesting them). Let's first consider the solution if every deputy minister only suggested two nodes. The solution would then be to increment a counter at the two nodes respectively, and decrementing a counter at the LCA of these two nodes by 2. Then, you would have to run a tree dp approach.
Now for multiple nodes that are suggested by one deputy minister, it gets a little bit more complicated. First, sort the nodes by their Euler Tour Indices. Consider nodes $$$c_1, c_2, ..., c_k$$$ to be sorted by their Euler Tour Indices. Then, if we were to traverse the nodes in the order $$$c_1 \to c_2 \to ... \to c_k \to c_1$$$, then each necessary edge would be visited exactly twice (going up and going down). If you now increment the counter at each of the nodes $$$(c_1, c_2), (c_2, c_3), ..., (c_k, c_1)$$$ by one respectively and decrement the counter at $$$LCA(c_1, c_2), LCA(c_2, c_3), ..., LCA(c_k, c_1)$$$ by two, and then run the tree dp, then you would have to check for each edge if the value is at least $$$2K$$$.
Interesting!
Can this solution be extended to solve the problem online?
That's the part that I didn't show on purpose for you to think a bit about it. If you couldn't come up with a solution:
It is basically the same approach, except for two things:
But when we decrement the counter we just remove one occurence what if four occurences are on the subtree of one node this will count the same occurence twice.
I'm sorry, but I don't think that I really understand your question
Try to submit your online solution on my problem and I will consider reviewing it.
I think I understood what you mean nice solution !
Can't open your solution ("You are not allowed to view the requested page").
Anyways, another fact.
Request on a $$$u$$$ subtree is a request on $$$[tin[u], tout[u])$$$ in euler tour
And changing $$$u$$$ is just request in $$$tin[u]$$$ point
Now we can just solve this task on the array as usual
Hmm. I will add the code as a spoiler. Try to submit your solution so I can understand what do you mean.
https://codeforces.com/gym/521454/submission/258990677
Isn't this MO's algorithm ?
It is. Just a way to make subtree queries -> array queries task which wasn't mentioned here.
Also there is merge-sort-tree log^2 solution, but it is much slower than MO in practice
I heard about such thing but I wanted to introduce the trick using HLD because I thought it is more general . Also I don't think alternative solutions work for operations that cannot be canceled though alternative solutions are much easier to code and after all most solutions use the same trick that I mentioned at the end of the blog.
Can you suggest me resources to put at the end of the blog in case if someone is interested in array distinct values queries?
With merge-sort-tree (or 2d tree as suggested here, but the main is the idea) https://codeforces.com/blog/entry/10508?#comment-158835
With MO (for sum we do the same but change the sum instead of count) https://codeforces.com/blog/entry/83630
Thank you!
Auto comment: topic has been updated by Haidora (previous revision, new revision, compare).
Auto comment: topic has been updated by Haidora (previous revision, new revision, compare).
I think instead of using HLD, we could solve this problem by using two Euler Tours (prefix and postfix node order) and two BITs. So we could solve this problem in O((n+q) log n)
Yes, but I wanted to introduce the solutions with HLD because of the idea to transform a subtree update to a path update which can be much easier to think about in some problems .After all, every possible solution is acceptable because this is an educational blog so try to submit your solution to check your understanding. Thank you for reading .
Maybe you can use the DFN to transform the subtrees into segments. What you need to do is solve the problem in an array.
What is DFN?
dfs the whole tree. The i-th visited vertex j is considered to have i-th dfn. i.e. $$$dfn[j]=i$$$.
In this way, a subtree can be represented with a range on dfn. Let $$$sz[i]$$$ be the number of vertexes in i's subtree. i's subtree = $$$[dfn[i],dfn[i]+sz[i])$$$.
I found smth similar to this in your words. Maybe not too many ppl call this "dfn".
It's usually called time-in or tin
In fact, today I met a problem like this. It needs to solve how many distinct values but not their sum. I used a fenwick tree with a segmenttree to maintain the $$$pre_i$$$ which means the max $$$j$$$ which $$$j < i$$$ and $$$col_j = col_i$$$. Its time is $$$O(q \log^2 n)$$$, and I got TLE due to the big constant problem. But there is someone who use the mo's algorthm which got AC in $$$O(n^{\frac{5}{3}})$$$...
Sorry, but I had great difficulty reading through it. I cannot understand why so many question marks make sense in a tutorial blog :(.
I will update this comment after I fully understand what you means. btw, the array version is Insects in the Mirror, which can be solved in $$$\mathcal O((n + q)\log^2)$$$. I'm pretty sure your method is as the same as this problem, but wait until I finish reading.
It's known that subtree query is weaker than range query and single point modification is weaker than range modification :/
What is the fastest way to do the problem for ranges with point modification?
It's still $$$\mathcal O(n\log^2n)$$$.
We can decompose this problem to "Counting points on a 3D plane".
Hmm I think I saw something that is similar to that using 2D sparse segment trees is this the same as your method?
Sorry, but I wanted to go step by step on how one can discover the solution himself.
It seems the method here is different.