[Tutorial] Sack (dsu on tree)

Revision en32, by Arpa, 2016-12-09 19:23:45

Update : added another method to code this technique (easy to code but n log ^ 2).

Update 2 : added another method to code this technique (easy to code and n log).

Update 3 : bugs in style 2 have fixed. And 2 new problems added.

Update 4 (15 August 2016) : A new problem (Sgu507) added to list.

Update 5 (20 September) : 2 new problems (291E - Древесно-строковая задача, 716E - Цифровое дерево) added to list.

Update 6 (6 December) : My invented style and 741D - Помеченное буквами дерево Arpa и забавные пути Mehrdad added to list.

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 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, int p){
    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, int p){
    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);
}

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];
    (*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 vertice 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];
    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 vertice v that has color c. You can answer the queries easily.
    // note that in this step *vec[v] contains all of the subtree of vertice 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 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);
}

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] ] ]++;
    //now cnt[c] is the number of vertices in subtree of vertice 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 - Деревянные запросы : 17961189 Thanks to Sora233; this problem is also good for start coding.

Sgu507 This problem is also good for start.

246E - Братья по крови возвращаются : 15409328

208E - Братья по крови : 16897324

291E - Древесно-строковая задача : See bhargav104's comment below : link.

343D - Водяное дерево : 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 - Дерево и запросы : 15449102 Again note that problem is not easy :)).

716E - Цифровое дерево : 20776957 A hard problem. Also can be solved with centroid decomposition.

741D - Помеченное буквами дерево Arpa и забавные пути Mehrdad : 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 PrinceOfPersia who taught me this technique.

Tags dsu on tree, sack, guni

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en44 English Arpa 2021-03-29 13:12:35 93 Tiny change: 'escribing my blog: [Li' -> 'escribing this blog: [Li'
en43 English Arpa 2020-09-01 10:35:41 41
en42 English Arpa 2018-07-28 04:37:19 92 added 1009F
en41 English Arpa 2018-06-14 13:03:31 110 fixed links for solutions
en40 English Arpa 2017-08-06 13:04:50 3 Tiny change: '/now (*cnt)[c] is th' -> '/now (*cnt[v])[c] is th'
en39 English Arpa 2017-08-06 13:00:28 3 Tiny change: '/now (*cnt)[c] is th' -> '/now (*cnt[v])[c] is th'
en38 English Arpa 2017-06-04 13:33:24 56 Fixed grammar mistakes using Grammarly.
en37 English Arpa 2017-03-11 15:17:48 98 Bug in second method fixed, thanks to Zhanbolat.
en36 English Arpa 2017-01-02 22:09:29 375 vertice -> vertex
en35 English Arpa 2016-12-22 08:03:21 223 race problem added
en34 English Arpa 2016-12-21 15:07:17 876 Added another problem (hacker earth). Added link to my solution for 741D. fixed the broken link. The word friend before AmirAz has been removed
en33 English Arpa 2016-12-09 20:44:30 22 Tiny change: ']++;\n ' -> ']++;\n cnt[ col[v] ]++;\n '
en32 English Arpa 2016-12-09 19:23:45 82
en31 English Arpa 2016-12-06 22:48:56 34
en30 English Arpa 2016-12-06 21:06:49 14 Tiny change: 'm:741D] : [submission:] A hard pr' -> 'm:741D] : A hard pr' (published)
en29 English Arpa 2016-12-06 14:43:47 2 Tiny change: 'Update 6 (5 December)' -> 'Update 6 (6 December)'
en28 English Arpa 2016-12-05 15:51:45 7
en27 English Arpa 2016-12-05 12:35:39 4 Tiny change: 'lem:741D] has added to ' -> 'lem:741D] added to '
en26 English Arpa 2016-12-05 08:11:21 1293 (saved to drafts)
en25 English Arpa 2016-09-20 17:11:40 262
en24 English Arpa 2016-09-20 14:23:10 61
en23 English Arpa 2016-09-20 14:22:04 134
en22 English Arpa 2016-08-15 15:07:32 232
en21 English Arpa 2016-05-17 18:41:24 1 Tiny change: 'ew problem added.\n\' -> 'ew problems added.\n\'
en20 English Arpa 2016-05-17 18:41:03 233
en19 English Arpa 2016-05-17 09:29:35 129
en18 English Arpa 2016-05-16 22:41:35 127
en17 English Arpa 2016-05-13 09:11:10 4
en16 English Arpa 2016-04-25 18:04:51 73
en15 English Arpa 2016-04-25 15:51:57 935
en14 English Arpa 2016-04-24 21:14:50 11
en13 English Arpa 2016-04-24 19:06:48 195 (published)
en12 English Arpa 2016-04-24 19:03:15 672 (saved to drafts)
en11 English Arpa 2016-04-24 18:08:54 18
en10 English Arpa 2016-04-24 17:54:16 33
en9 English Arpa 2016-04-24 17:16:11 53 Tiny change: 'se of this code work' -> 'se of this, code work' (published)
en8 English Arpa 2016-04-24 15:33:44 88
en7 English Arpa 2016-04-24 15:18:06 144
en6 English Arpa 2016-04-24 15:02:14 15
en5 English Arpa 2016-04-24 15:01:27 796
en4 English Arpa 2016-04-24 14:34:52 294
en3 English Arpa 2016-04-24 14:28:47 1545
en2 English Arpa 2016-04-24 14:03:34 1027 Tiny change: 'ample:\n\nWe have a tree, e' -> 'ample:\n\ngiven a tree, e'
en1 English Arpa 2016-04-14 15:11:39 26 Initial revision (saved to drafts)