What is the dsu on tree?

A2OJ's DSU Section has quite a few tree DSU problems.

Thank you for this post, it explains the theory well and is very easy to read.

What does the variable "keep" denote ?

In second easy with O(n*lg n)

Why if(keep==false) we delete only vertex from main vector

for(auto u : *vec[v])
            cnt[ col[u] ]--;

but we don't delete vertex from cnt which we changed here:

for(auto u : g[v])
       if(u != p && u != bigChild){
           for(auto u : *vec[u])
               cnt[ col[u] ]++;
       }

can someone tell me how 208E is solved with this technique? thanks a lot.

If i haven't read this article, i wouldn't get ac on this problem. It is another problem which can be solved easily by dsu.

here is my code in HLD-style.

Thanks!

I can't understand why the second code is correct...

Consider this example:

We wanna calculate the cnt for Vertex 8. These are the steps:

Going to Vertex 1

Going to Vertex 2 by keep=0

Going to Vertex 3 by keep=0,Vec[3]={3}

Going to Vertex 4 by keep=1,Vec[4]={4},Cnt[color[4]]=1

Going back to Vertex 2,Vec[2]={2,4},Cnt[color[4]]=0,Cnt[color[3]]=1

And then when we go to Vertices 5,6,7,8 still Cnt[color[3]]=1.

Also sorry if I did the steps wrong...

UPD Thank you for editing the blog. My problem fixed.

Great post. If you explained the idea before showing the code, it would be better to understand. Also commenting the variables meaning in the code would be of great help.

It would be good to mention that most solutions will answer the queries offline, which may be a problem sometime (maybe someone didn't notice this lol).

Also, it would be nice to post hints about the solutions.

Proving explicitly why it is nlogn would be good too (ie. as each node's subtree set gets merged into one set of size equal or greater, and the base set has size 1 and the last set has size n, then we take logn steps to go from 1 to n. Summarizing, each node gets merged logn times, so the total complexity is O(nlogn)).

Here's my solution to 343D, maybe it will be of help to someone: 18958875. A lot easier to code than the one in the tutorial.

In easy to code but O(nlog^ 2), I cant't understand why do we store the size of subtrees of vertices in array sz and use it as the criteria for choosing the big child, I think we should store in the array "sz" the number of distinct colors in the subtree of any node v, because that is what we actually iterate on when transferring the map from v to u, why is this wrong?

Ahh, thanks gabrielsimoes, for anyone struggling to understand: n*log^2n is about answering queries OFFLINE right during the dfs. After the dfs has finished the cnt[v] will no longer be a valid map for vertices that were chosen as bigChild.

http://codeforces.com/problemset/problem/291/E 291E - Tree-String Problem Arpa This problem can also be done by dsu on trees. Calculate hash value for each suffix value of target string. Then for each suffix of an edge if it is a valid prefix of the target string we would just need the frequency of the hash value of the remaining suffix of the target string in its subtree which can be maintained by this technique. The case when the entire string occurs in an edge can be dealt with separately.

Actually, in China, we call this method as "Heuristic Merge" which always merge the smaller to the bigger. Not hard to understand each vertex will be visited in O(log n) times because when we visited a vertex, then the size of tree which the vertex is in doubled.

Hey Arpa,

In your my invented style I'm unable to understand that why in third loop are you not checking for u not being parent of v. Why are you only checking for just u not being the big child.

Thanks in Advance

In the easy to code O(nlogn) method vec[v] stores all the vertices in the the subtree rooted at v . How will this fit into memory if we are not deleting the vec of child after merging it with the parent

Hi Arpa, I can not understand, why is this approach called dsu on tree? This approach has a nice trick to reduce complexity by saving data about "big child". I can't see any special similarity with general dsu approach. In general dsu problems, we merge 2 subset into 1 set by linked list approach. But, in your tutorial there is no "merge" function. Am I missing something?

Also I see that, in your 600E's solution 14554536 you used merge functon. I can't understand, could you please explain that code?

Hi Arpa! Thanks for making this tutorial.

I just want to make sure my understanding is correct: this merging smaller maps into larger ones takes logarithmic time because when a vertex is merged, the new map it is in at least twice its size. Hence, merging can only happen log(n) times for each of the n vertices, leading to a total runtime of O(nlogn)?

Thanks!

Why do we need to iterate through the children of v after add(v,p,-1)in the naive approach?

101 Hack 47 Summing Tree was solved using this technique by satyaki3794 Submission

also 778C - Peterson Polyglot is solvable with a similar tecnique: is that DSU on tree?

Can anyone give me a link to "Shaazzz contest round #4 (season 2016-2017) problem 3" or tell me where can I find it? Thanks.

APIO 2016 Fireworks uses this, but is a much harder problem.

Arpa, in the Easy to code but O(nlog²n) section code you have written a commented line that is : //now (*cnt)[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily.. But I think it would be //now (*cnt[v])[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily.. Will (*cnt)[c] changed with (*cnt[v])[c] ?

You can solve APIO 2012 Dispatching with this technique too.

IOI 2011 — Race What is the idea of DSU on tree for this problem? I know of a solution based on Centroid Decomposition.

914E - Palindromes in a Tree can solve with sack too, Arpa :)

ps: for this problem centroid decompose works too... :)

can anyone please explain how to solve 716E using this technique?

In the contest 600, no one can view other's submissions except his own.

That's why no can see your submissions for 600E - Lomsat gelral except you.

So, please give alternating link of your solutions for the first problem in the list, 600E - Lomsat gelral

Another problem which can be solved by this technique: Coloring Tree
Its easier than 600E - Lomsat gelral.

One more : 932F - Escape Through Leaf

No good explanation! Only code! Worst tutorial.

Nice tutorial!

and also happy Nowruz:)

For those who still confused about the time complexity, I found this explanation by radoslav11 helps a lot.

What is col[v]?

I loved the way you used the Euler tour sequence to iterate through the subtrees. My 2 cents is a way to use C++ to implement this nicely. The main idea is to use a structure, that keeps pointers instead of st[v] and ft[v], and to give it a begin() and end() member function, so that you can iterate through it with

for(int u : T[i])
    cout << u << " is in the subtree of " << i << "\n";

To actually solve the problem, maybe in a Heavy-Light style, I kept also for each vertices a pointer to the leaf of its heavy-path, so that I could only change the answer in the leaf.

My full implementation of lomsat gelral can be found here

Hi , Arpa, I used this technique to solve 600E - Lomsat gelral, its a very neat technique.. but wont this get a MLE? I am getting a MLE with the O(nlog^2n0 method ,.. I saw your solution and I see its the same as mine, but mine gets MLE.. My solution :- 39325497

Great blog but I am not able to understand the logic behind the O(nlogn) solution it would be a great help if anyone can explain it.

I have a question for style 3 i.e HLD style.
I'm not so sure what's happening in there, I have 2 assumptions. Both of them are wrong, so it would great if someone could point out the mistake and explain what's right.

We are in root.

1. We first go down the light edges of root and when we finish with them, we clear the cnt array, so there is absolutely nothing left in it and then we proceed to the heavy child of the root and then we just update cnt array.
   Now we go back to the light edges of the root and (here's the problem) as the cnt array only contains information for the heavy child of the root, we must go through EVERY vertex in subtrees of light children of the root. If we don't go to the heavy children in the subtrees (as it proposes in tutorial?), then the answer is wrong, as we didn't count them (remember that we cleared the cnt array).

2. We first go down the light edges of the root, but this time, for every heavy child, we keep the information.
   But then as we proceed to the heavy child of the root, the array cnt won't be empty and the answer for heavy child will be incorrect.

Another problem can be solved with this technique. Arpa please add this one in the list.

http://codeforces.com/contest/1009/problem/F (Dominant Indices)

Can someone explain why this solution 40510312 is getting TLE on problem 600E - Lomsat gelral. I'm using style 4.

I'm continuously getting TLE in test case 30 in 570 : D : Tree Request (The second one given in the blog practice problem) while implementing through DSU similar to what is given here. Submission Id : 40780911 , can somebody make a look over this and provide hint to optimize it.

This blog was a bit code-heavy for me when I first read this. Hence I have tried to simplify the concept a bit more in a more textual fashion in my own tutorial spin-off. I have tried to provide the intuition behind small-to-large merging including small to large on trees, also knows as DSU on trees.

However I. haven't provided any code as the code given by the OP is more than enough.
DSU-on-Tree-Intuition

sorry but you absolutely wrong about the complexity, i know the trick merge smaller to greater but it works when you don't for(i = 0; i < greater.size(); i++) again, but here in O(nlogn ^ 2) you use cnt[v] = cnt[bigchild], it equal to "for(int i = 0; i < cnt[bigchild].size(); i++) {} ", so it's not O(nlogn ^2)

Can someone explain, why will the complexity of the first code will be O(nlog^2n)?

This particular problem can be solved in linear time:

int cnt[maxn];

void dfs(int v, int p){
    // Subtract cnt[c] for query here, e.g. answer[query] -= cnt[c];
    
    cnt[col[v]]++;
    for(auto u : g[v])
        if(u != p)
            dfs(u, v);

    // Add cnt[c] for query here, e.g. answer[query] += cnt[c];
}

Can somebody help me understand why my solution 51874074 for problem 246E - Blood Cousins Return gets WA on test 50? I tried to implement the Heavy Light Decomposition style dsu

How to answer online queries using this technique??

why did he declare every time using pointer, can't we simply declare array of map for first approach as map<int,int> cnt[maxx] instead of map<int,int>*cnt[maxx] ?

Why is my code getting TLE for problem 600E — Lomsat gelral? I'm using the technique no. 1 from this tutorial.

Love this.

Thank you for the article.Now I understand it.

Small nitpick: In solution 2, the comment

//now (*cnt[v])[c] is the number of vertices in subtree of vertex v that has color c.

should be:

//now cnt[c] is the number of vertices in subtree of vertex v that has color c.

For everyone who needs an explanation, here is a blog.

And obviously, thank you Arpa for this wonderful content!

Thanks a lot really.

For heavy-light decomposition style for the first add(v,p,1) except the big child sub-tree we are visiting the whole sub-tree of all the light children. Also for second add we are visiting again all the sub-tree if keep==0. How does the complexity becomes $$${O(nlogn)}$$$. Having a hard time to understand, please can anyone tell me how is the complexity calculated.

Can we know the shortest distance from a vertex using dsu ?

I tried solving 208E - Blood Cousins using the first approach as explained in this blog but getting MLE on test case 59. I'm not able to figure out why it's giving MLE. Please help!

Here is the link to my submission : 80790329

Thanks!

https://www.hackerearth.com/problem/algorithm/monkeys-on-a-tree-0fe98ed9/

This problem can also be done by dsu on trees.

cnt[v] = new map<int, int> ();

Why are we doing this? My code gave segmentation fault without this.

Very late, but this problem (Educational Round 91 E) is a very recent problem that can be solved with this technique.

Nice

Hello AmirAz, I tried to submit a similar solution to yours for the problem Water Tree but it was giving tle on case 20. Can you tell me what to did you exactly took care of to reduce time complexity?

Great practice problems! Thanks for the tutorial Arpa.

Sorry for necroposting.

I felt this could be helpful for people trying to learn this great technique.

https://codeforces.com/problemset/problem/1363/E

My submission: https://codeforces.com/contest/1363/submission/125449811

Very useful blog! Thank for Arpa. I also looking forward to seeing an update on the problem list as there are many new forms of problems to be solved by this technique nowadays. As far as I know, some problems can even be associated with data structures, such as this.

Is there any possible way to solve SGU507 by this technique? Please tell me, thanks a lot.