| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | SecondThread | 145 |
| 9 | pajenegod | 145 |
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