[Tutorial] dsu on tree

Правка en3, от Arpa, 2016-04-24 14:28:47

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);
}

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 chains only and because of that, code works in O(n log n) time.

Теги dsu on tree, sack, guni

История

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