Блог пользователя huzaifa242

How to handle updates in DSU on trees
Автор huzaifa242, история, 7 лет назад, По-английски

I read this Blog on DSU on trees.

Now, I have a doubt.

Given a tree with n nodes and each node has some color c[i], following query needs to be answered

1 x y: change color of node x to y

2 u c: count all the nodes with color c in subtree of u.

How to approach this??

Thanks for help in advance.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
7 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

Do a preorder traversal/euler tour on the tree so that colors of nodes in the same subtree will be together. Now, you just need to keep a segment tree, with order statistic set in each node. I think that you can take it from here.

→ Ответить
»
7 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

actually u can solve this problem without a segment tree. Basically, u maintain n (of the n colors) binary search tree (seems difficult? Rmb pbds exits) in each of the BST, stores the order of the node in the euler tour. After that, a simple, lower_bound and upper_bound operation can solve the problem.

Memory: O(N), Time: O(N log N)

→ Ответить