Recently I have come across a problem of an IUPC contest, where the problem asks for the summation of the mex value of all subtrees of a tree for each vertex where the vertex is the root of the tree. The detailed statement is given below or can be found in I-Mexy.
Can anyone give me hints or provide any resources about this topic?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3390 |
| 6 | Um_nik | 3387 |
| 7 | tourist | 3384 |
| 8 | heuristica | 3322 |
| 9 | turmax | 3319 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 144 |
| 5 | AmShZ | 139 |
| 5 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | maroonrk | 134 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
Auto comment: topic has been updated by babjamal (previous revision, new revision, compare).
Auto comment: topic has been updated by babjamal (previous revision, new revision, compare).
Auto comment: topic has been updated by babjamal (previous revision, new revision, compare).
You can do this with Small-to-Large merging in O(N * log^2 N) time, search on USACO Guide for small-to-large there is a topic.
OK I have been able to solve the problem using this technique for a single rooted tree. But what about to solve the problem for each root/vertex?
Oh, I didn't read that part of the problem, my bad I thought it was for a single root only!
probably it can be (over)solved by root rotating and mex on segment queries.
supporse we know mex for each subtree initially (root=0). if r is root and c its child we can rotate this edge to make c as root. how will mexes change? mex(c) will be mex of all numbers and mex(r) will be mex of numbers except subtree of c (current subtree)
so current subtree is defined by oriented edge. in tree with root 0 this will be subtree or... undertree (how to call it better?). if we concate euler tour of tree twice than both subtree and undertree becomes segment. and we can ask mex on segment in O(logn).
upd (I got AC). ok we need only mex of each subtree (for init) and mex for each not subtree (for rotating). this can be found somehow easy or by mex on segments query (O(qlogn)).
Hi, I am the author of this problem. Nice to randomly find this thread discussing my problem, and it's great that you found the solution.