minhi1's blog

By minhi1, history, 7 months ago, In English

Given a tree with n nodes and n — 1 edges. There are total k different colors (k <= n). Each node i has a color c(i) (1 <= c(i) <= k). Cost of a subtree u equals number of distinct colors in subtree u.

Given q queries. Each query belongs to two types: Type 1: (1, u, nw) is to change the color of node u to nw. (1 <= nw <= k) Type 2: (2, u) print the Cost of subtree u.

Constraints: 1 <= n <= 5e5 1 <= q <= 3e5

So far I have only thought of counting distinct colors without updating queries by small-to-large or BIT. For updating, I just know that type 1 query will affect all the ancestors of u. Still, I don't know the optimized way yet. Can you guys help me ? Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by minhi1 (previous revision, new revision, compare).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If you have BIT then type 1 = tree.point_update(), type 2 = range_query(time_in[u], time_out[u]) times are from dfs-order

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How can I upd in type 1. I'm stuck at it