| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
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