Need help in dsu on trees tutorial.

Revision en1, by Shahriar_CSECU, 2018-07-18 15:09:35

In this tutorial first code is :

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];
    else
        cnt[v] = new map<int, int> ();
    (*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[v])[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily.

}

In comment author told that "now (*cnt[v])[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily."

But I can't answer the queries.I can't implement the query function my self.I tried it for a long time but failed.Can anyone implement it for me.It will be great help.

Thanks in advance.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Shahriar_CSECU 2018-07-18 15:09:35 1127 Initial revision (published)