Euler tour problem
Разница между en1 и en2, 1 символ(ов) изменены
Given a tree with n nodes and n &mdash; 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский minhi1 2024-04-06 20:21:48 1 Tiny change: '= nw <= k) \nType 2: ' -> '= nw <= k)\nType 2: '
en1 Английский minhi1 2024-04-06 20:20:26 715 Initial revision (published)