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

The obvious 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 vertex v that has color c
    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 vertex v that has color c
    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. it runs dfs on biggest child of every vertex only once.

If you know 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 teached me this technique.