**Changes are available in history section.**

Hi!

Most of people know about dsu but what is the "dsu on tree" ?

In Iran, we call this technique "Guni" (the word means "sack" in English), instead of "dsu on tree".

I will explain it and post ends with several problems in CF that can be solved by this technique.

# What is the dsu on tree?

With dsu on tree we can answer queries of this type:

How many vertices in subtree of vertex `v`

has some property in O(n lg n) time (for all of the queries).

For example:

Given a tree, every vertex has color. Query is **how many vertices in subtree of vertex v are colored with color c?**

Lets see how we can solve this problem and similar problems.

First, we have to calculate size of subtree of every vertice. It can be done with simple dfs:

```
int sz[maxn];
void getsz(int v, int p){
sz[v] = 1; // every vertex has itself in its subtree
for(auto u : g[v])
if(u != p){
getsz(u, v);
sz[v] += sz[u]; // add size of child u to its parent(v)
}
}
```

Now we have size of subtree of vertex `v`

in `sz[v]`

.

The naive method for solving that problem is this code(that works in O(N ^ 2) time)

```
int cnt[maxn];
void add(int v, int p, int x){
cnt[ col[v] ] += x;
for(auto u: g[v])
if(u != p)
add(u, v, x)
}
void dfs(int v, int p){
add(v, p, 1);
//now cnt[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily.
add(v, p, -1);
for(auto u : g[v])
if(u != p)
dfs(u, v);
}
```

Now, how to improve it? There are several styles of coding for this technique.

### 1. easy to code but .

```
map<int, int> *cnt[maxn];
void dfs(int v, int p){
int mx = -1, bigChild = -1;
for(auto u : g[v])
if(u != p){
dfs(u, v);
if(sz[u] > mx)
mx = sz[u], bigChild = u;
}
if(bigChild != -1)
cnt[v] = cnt[bigChild];
else
cnt[v] = new map<int, int> ();
(*cnt[v])[ col[v] ] ++;
for(auto u : g[v])
if(u != p && u != bigChild){
for(auto x : *cnt[u])
(*cnt[v])[x.first] += x.second;
}
//now (*cnt)[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily.
}
```

### 2. easy to code and .

```
vector<int> *vec[maxn];
int cnt[maxn];
void dfs(int v, int p, bool keep){
int mx = -1, bigChild = -1;
for(auto u : g[v])
if(u != p && sz[u] > mx)
mx = sz[u], bigChild = u;
for(auto u : g[v])
if(u != p && u != bigChild)
dfs(u, v, 0);
if(bigChild != -1)
dfs(bigChild, v, 1), vec[v] = vec[bigChild];
else
vec[v] = new vector<int> ();
vec[v]->push_back(v);
cnt[ col[v] ]++;
for(auto u : g[v])
if(u != p && u != bigChild)
for(auto x : *vec[u]){
cnt[ col[x] ]++;
vec[v] -> push_back(x);
}
//now (*cnt)[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily.
// note that in this step *vec[v] contains all of the subtree of vertex v.
if(keep == 0)
for(auto u : *vec[v])
cnt[ col[u] ]--;
}
```

### 3. heavy-light decomposition style .

```
int cnt[maxn];
bool big[maxn];
void add(int v, int p, int x){
cnt[ col[v] ] += x;
for(auto u: g[v])
if(u != p && !big[u])
add(u, v, x)
}
void dfs(int v, int p, bool keep){
int mx = -1, bigChild = -1;
for(auto u : g[v])
if(u != p && sz[u] > mx)
mx = sz[u], bigChild = u;
for(auto u : g[v])
if(u != p && u != bigChild)
dfs(u, v, 0); // run a dfs on small childs and clear them from cnt
if(bigChild != -1)
dfs(bigChild, v, 1), big[bigChild] = 1; // bigChild marked as big and not cleared from cnt
add(v, p, 1);
//now cnt[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily.
if(bigChild != -1)
big[bigChild] = 0;
if(keep == 0)
add(v, p, -1);
}
```

### 4. My invented style .

This implementation for "Dsu on tree" technique is new and invented by me. This implementation is easier to code than others. Let *st*[*v*] dfs starting time of vertex *v*, *ft*[*v*] be it's finishing time and *ver*[*time*] is the vertex which it's starting time is equal to *time*.

```
int cnt[maxn];
void dfs(int v, int p, bool keep){
int mx = -1, bigChild = -1;
for(auto u : g[v])
if(u != p && sz[u] > mx)
mx = sz[u], bigChild = u;
for(auto u : g[v])
if(u != p && u != bigChild)
dfs(u, v, 0); // run a dfs on small childs and clear them from cnt
if(bigChild != -1)
dfs(bigChild, v, 1); // bigChild marked as big and not cleared from cnt
for(auto u : g[v])
if(u != p && u != bigChild)
for(int p = st[u]; p < ft[u]; p++)
cnt[ col[ ver[p] ] ]++;
cnt[ col[v] ]++;
//now cnt[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily.
if(keep == 0)
for(int p = st[v]; p < ft[v]; p++)
cnt[ col[ ver[p] ] ]--;
}
```

But why it is ? You know that why dsu has time (for *q* queries); the code uses same method. Merge smaller to greater.

If you have heard `heavy-light decomposition`

you will see that function `add`

will go light edges only, because of this, code works in time.

Any problems of this type can be solved with same `dfs`

function and just differs in `add`

function.

Hmmm, this is what you want, problems that can be solved with this technique:

(List is sorted by difficulty and my code for each problem is given, my codes has `heavy-light`

style)

600E - Lomsat gelral : `heavy-light decomposition`

style : 14607801, easy style : 14554536. I think this is the easiest problem of this technique in CF and it's good to start coding with this problem.

570D - Tree Requests : 17961189 Thanks to Sorasorasora; this problem is also good for start coding.

Sgu507 (SGU is unavailable, read the problem statements here) This problem is also good for start.

HackerEarth, The Grass Type This problem is also good for start (See bhishma's comment below).

246E - Blood Cousins Return : 15409328

208E - Blood Cousins : 16897324

IOI 2011, Race (See SaSaSaS's comment below).

291E - Tree-String Problem : See bhargav104's comment below.

343D - Water Tree : 15063078 Note that problem is not easy and my code doesn't use this technique (dsu on tree), but AmirAz 's solution to this problem uses this technique : 14904379.

375D - Tree and Queries : 15449102 Again note that problem is not easy :)).

716E - Digit Tree : 20776957 A hard problem. Also can be solved with centroid decomposition.

741D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths : 22796438 A hard problem. You must be very familiar with Dsu on tree to solve it.

For persian users there is another problem in Shaazzz contest round #4 (season 2016-2017) problem 3 that is very hard problem with this technique.

If you have another problems with this tag, give me to complete the list :)).

And after all, special thanks from amd who taught me this technique.

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 ?

The way I understand HLD here is basically if a child is the big child, we don't want to recompute answer for it to reduce computation. So we just store the answer for it in the

`cnt`

array already so that it's parent doesn't need to re-dfs this subtree.`keep`

denotes whether or not this child is that big child. Please correct me if I'm wrong. :)Look at last two lines:

It means that if

`keep == false`

after`dfs`

clear`v`

s subtree information from`cnt`

. And if`keep == true`

, don't clear`v`

s subtree information from`cnt`

. In other word if`keep == true`

after calling`dfs`

, for each`u`

from subtree of vertice`v`

,`col[u]`

is in`cnt`

(`cnt[ col[u] ]++`

).And NibNalin is right.

`keep`

is`true`

if and only if`v`

is biggest child of it's parent.Hi Arpa, thanks a ton for this awesome post. I have really learnt lot from it.

I do have one question though. What is the advantage of having keep=false? If that part is kept as it is, without clearing, doesnt the computation become faster? Can you please help clearing this doubt?

Hi, Thanks.

Consider vertex v has two children, q and p. If you call dfs for both of them with keep = true, they will mixed up their information, and queries will be incorrectly answered.

oh..ok. Got it now. Thanks.

Observations to understand the complexity:

`dfs`

function visits each node exactly once.`n^2`

. Note that in the`add`

function, we only go down from a vertex to its children if the edge connecting the vertex to the child is a light edge.You can think of it in this way, each vertex

`v`

will be visited by a call to the`add`

function for any ancestor of`v`

that is connected to a light edge. Since there are at most`log(n)`

light edges going up from any vertex to the root, each vertex will be visited at most`log(n)`

times.So the algorithm is: Say you are at a vertex

`v`

, first you find the bigchild, then you run dfs on small childs, passing the value of keep as`0`

. Why? So they are cleared from cnt. Then you run a dfs on bigchild, and you do not clear it from`cnt`

. Now,`cnt`

stores the results for all vertices in the subtree of`bigchild`

(since we cleared`cnt`

for small childs and didn't do so for the bigchild), so we call the`add`

function to "add" the information of children of current vertex that are connected to it via a light edge. Now we are ready to compute the answerIn second easy with O(n*lg n)

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

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

There was a mistake in writing. I'm sorry.

Thanks for reporting this problem.

code should be:

Instead of:

I have edited that.

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

You need to compute for each pair

`v p`

the p-th cousin of v. That is equivalent to finding the number of p-th descendants of the p-th ancestor of`v`

— 1.So for each query, replace

`v p`

with`p_th_ancestor_of_v p`

. Now you need to store in`cnt`

the number of nodes at a certain depth. In other words,`cnt[x]`

should be equal to number of nodes at depth`x`

in the current subtree.Code for Reference: http://codeforces.com/contest/208/submission/17513471

can't understand why for every vertex v we ans[depth[v]] increase by 1 when we call add function,why must we do it?or why it must be ans[deth[v]] when depth[v] means distance from root to v?

`ans[h]`

is equal to number of vertices with height h, (with distance h from root).Let par, p'th ancestor of v, the answer to query is:

Consider only subtree of vertice par, print ans[ height[v] ] — 1.

So with method above we can process all of the queries.

See my code for better understanding.

thanks everyone , now i understand.

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!

Thanks! Added to list ;)

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...

UPDThank 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

nlognwould 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 sizen, then we takelognsteps to go from 1 ton. Summarizing, each node gets mergedlogntimes, so the total complexity isO(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.

Thanks for your suggestions first !

I proved that it is O(nlogn) :

You know that why dsu has O(q log n) time (for q queries); the code uses same method. Merge smaller to greater.And about your code (18958875), anyone has a different opinion !

Thanks for the reply!

Yeah, you did prove. People who remember DSU's proof will most likely understand. I stated a more extensive proof would be better thinking about people who don't exactly know the proof. Don't take me wrong, but they may get a little confused reading this proof.

I mentioned my code exactly because everyone has a different opinion,. Maybe it'll help a later reader, that's all.

Sorry this might be a stupid question to bring up, but why is the complexity of the heavy-light decomposition style one in

O(nlogn)?In the case where each node has at most two children: Denote the root node of the tree as

u, which is of sizes. The child ofuconnected to the lighter edge is of size at most . So the total number of nodes on which we run the "add" function would be at most . So I don't understand where thelog(n) factor comes from.The online tutorial for HLD says a new chain is built when we arrive at a child node via a lighter edge, where each chain is stored as a segment tree, and so I can see there is indeed a

O(logn) factor involved.Regardless can you perhaps elaborate a little bit more on the time complexity of the dsu structure? Thank you!

Hi !

The online tutorial for HLD says a new chain is built when we arrive at a child node via a lighter edge, where each chain is stored as a segment tree, and so I can see there is indeed a O(logn) factor involved.As you know, if you use

`segment tree`

in`heavy-light decomposition`

, each query time complexity will beO(log^{2}(n)). Because in each query you will goO(log(n)) chains and in each chain it will spendO(log(n)) time.Now, I will proof that "heavy-light decomposition style implementation" of "dsu on tree" is

O(n.log(n)):Consider a complete binary tree with n vertices. In dfs function you will run another dfs function in child (

T(n/ 2) * 2) and you will call`add`

function and it will spendO(n/ 2) time. So,T(n) =n/ 2 + 2 *T(n/ 2) =O(n.log(n))Pardon me , but I don't follow. Which dsu are you talking about? The one with inverse-Ackermann function?

No. Dsu with size compare. Like this :

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?

Hi !

It isn't wrong! Both of your method and mine have the same worst case. But your average is better.

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.

Thanks added to list, but it can be solved very easier : 19827525, just use KMP.

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

Sorry, fixed. It's because I've copied my code from 741D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths, input for this problem was a rooted tree.

Thanks a lot,

Also, I think there is one more mistake. You never added col[v] to the array. Am I missing something. Thanks in advance.

You are right, I'm very thankful to you. I was careless while coping the code from polygon.

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 parentUsed memory is always less than or equal to time complexity, so when time complexity is , used memory is less than or equal to . In this case, used memory is . Although if you delete useless

vec's the memory become .Thanks for the reply . I think this problem can also be solved using your approach. (The Grass Type HackerEarth)

I'll add this problem to the post if I find it related, I'm thankful anyway.

Edit: Note that this is notmyapproach, but I'm the first man who publishes a tutorial about this (not sure), Sack has been used in INOI, IOI and ACM several times, so it isn't a new thing, invented be me.Edit: Added.Can you mention probelms from the IOI that are solved with sack ?

I'll add one of them tonight.

Edit: Added.Wow, I didn't think of solving it with sack.Thx

Hi Arpa, I can not understand, why is this approach called

dsuon 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?

In fact we are merging information of small children with big child. Think more.

In that code,

mrgfunction merges information inuintov.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 thenvertices, leading to a total runtime ofO(nlogn)?Thanks!

Yes, but note that if you use map, it's .

If you use unordered_map, does it become

O(n·logn), then?Unordered_map is theoretically

O(n) per query. But you can suppose that it's O(1) per query in code.This 758E.Read this comment on how to use it.

Why do we need to iterate through the children of v after

`add(v,p,-1)`

in the naive approach?dfs() solves the problem for all the nodes, not just one. So, after you've gotten the answer for v, it will calculate the answer for its children.

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?

yes