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.
Auto comment: topic has been updated by huzaifa242 (previous revision, new revision, compare).
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.
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)
Thanks for this approach.
But I wanted to know if something can be done using that blog?? I mean ca we handle updates using the technique mentioned in the blog??
I don't think so, cuz the result in each node is used by its ancestor
Updating in this manner will be linear with a worst-case complexity of O(TN) where T is the number of updates