coder_with_h's blog

By coder_with_h, history, 4 weeks ago, In English,

Given a graph with N nodes and M edges. Each node is painted in one of N colors initially. There are Q queries of the following form: Repaint a single node to the given color. After performing each query, output the number of edges having both endpoints of the same color.

Can anyone please help me solve this problem?

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it
Hint
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please elaborate

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      1) We count number of edges having both endpoints of the same color before the quries. It will be ans.

      2) Divide nodes to 2 groups: 1 group: Nodes, which have more than sqrt(n) child. 2 group: Other nodes.

      3) For query for 1 type: if is it node from 1 groups: we just upd color, color[v] = col. else as they have less than sqrt(n) childs, we just going to childs and update ans.

      4) We will go with nodes from 1 groups, update answer like this: ans -= cnt[ls[v]][v] ans += cnt[color[v]][v] where, cnt[x][v] is number of nodes which have color x and it is child of v. ls[v] = it is last color of v. Memory limit will be Sqrt(n) * N.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        cnt[x][v] is number of nodes which have color x and it is child of v. The number of different colors is n and the number of nodes is n the memory limt will be n*n ??

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          cnt[x][v], it is array for nodes in 1 groups. The number of nodes, which have more than sqrt(n) child, will be less than sqrt(n), so we have Sqrt(N)*N.