Shahriar_CSECU's blog

Need help in dsu on trees tutorial.
By Shahriar_CSECU, history, 6 years ago, In English

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.

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

So firstly you create N vectors, call them qry[N]. Then, when you get a query, insert it into the vectors like below.

cin >> q;
for (int i = 0; i < q; i++) {
	int v, c;
	cin >> v >> c;
	qry[v].pb(make_pair(c, i));
}

Then simply for node v currently, just iterate over qry[v] and answer the queries respectively. Since you asked for implementation, it's just simply like this:

for (auto i: qry[v]) {
	ans[i.second] = cnt[v][i.first];
}
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I want to count the sum of color values of those color which appears maximum time in subtree of vertex v. Where color value <= n and n is number of nodes in tree.

    I want to solve this problem using dsu on trees.But can't apply the query for counting sum of color value for all node.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Well, for 600E a different approach is required. Save 2 values for each node, namely max and cur.

      Max will save the maximum appearance a color can get inside a node, while cur save the total sum of color appearing max times. A few modifications are required:

      • When obtaining bigChild, mx[v] and cur[v] must be updated to the bigChild's variables (Since you practically copy the map over, its max and sum will also be shared)
      for(auto u : g[v])
     if(u != p && u != bigChild){
           for(auto x : *cnt[u])
               (*cnt[v])[x.first] += x.second;
     }

      Just add a few lines to process mx and cur:

      When cnt[v][x.first] is updated, compare mx[v] with its new value:

      +) If mx[v] is bigger than cnt[v][x.first], nothing happens

+) If mx[v] is equal to cnt[v][x.first], cur += cnt[v][x.first]

+) If mx[v] is smaller, cur is resetted to 0 then added with cnt[v][x.first], also don't forget to update mx[v] itself

      Then the final answers are simply cur values of all nodes.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Alhamdulillah! Ac! Allah gave me ability for Ac.And Thank you bro.You helped me a lot.You described the solution clearly and detail.Thanks again.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I doubt that he helped you, but not you to yourself.

          → Reply