Hi!

Most of people know about dsu but what is the "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 vertice `v`

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

For example:

Given a tree, every vertice has color. Query is **how many vertices in subtree of vertice 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 = 0, int p = -1){
sz[v] = 1; // every vertice 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 vertice `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 = 0, int p = -1){
add(v, p, 1);
//now cnt[c] is the number of vertices in subtree of vertice 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);
}
```

And this code has O(n lg n) time !

```
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 vertice v that has color c. You can answer the queries easily.
if(bigChild != -1)
big[bigChild] = 0;
if(keep == 0)
add(v, p, -1);
}
```

But why it is O(n log n)? You know that why dsu has O(q log n) 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 O(n log n) time.

Any problem of this type can be solved with same function `dfs`

and only differs in function `add`

.

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)

600E - Lomsat gelral : 14607801 (I think this is the easiest problem of this technique in CF and it's good to start coding with this problem)

246E - Blood Cousins Return : 15409328

208E - Blood Cousins : 16897324

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

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

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

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