Hi!

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

I will explain it and post ends with several problmes 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 vertexes on 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 vertexes 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 vertex. it can be done with simple dfs:

int sz[maxn];
void getsz(int v = 0, int p = -1){
    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].