I recently got to know about Tree Flattening using a DFS Traversal. Can someone suggest some nice problems on the same. Thanks!
→ Обратите внимание
До соревнования
Codeforces Round 940 (Div. 2) and CodeCraft-23
3 дня
Зарегистрироваться »
Codeforces Round 940 (Div. 2) and CodeCraft-23
3 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.04.2024 05:38:26 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Recent,very good problem from July long challenge.Chef and Dragon Dens
I solved that one using 3 Segment Trees :/
It can be done with two Binary Indexed Trees.
Yeah actually the third SegTree was for RMQ ...
Uh? It is just saying the value at some position and update a range by adding a value to all elements in the range. It just a BIT/SegmentTree; since there are queries forward and backward you need two BIT/ST.
Yeah, I used 2 Lazy Segment Trees for Queries (Foward and Backward).
I used 3rd Segment tree for finding Largest Height between any range [L, R]. (Which is basically a RMQ — Range Maximum Query)
After flattening?
No, I did not flatten the Tree in that question. I used a Prefix-Sum Like Approach to solve the problem.
Initially I tried to do same, but I wasn't able to handle update query in log(n) so I got only 45 pts. What was your logic?
Lazy Updates can be done in O(logN).
And also, it is important to notice that heights are fixed.
The updates are on the tastiness only.
let's say $$$dp[u]$$$ is the sum of values of nodes on the path from root downto $$$u$$$. When an updates comes (sum a value of $$$x$$$ to the value of node $$$u$$$), $$$dp[v] \ \forall v\in subtree(u)$$$ are affected with a $$$+x$$$ increase, and when a query $$$u\rightarrow v$$$ comes (with $$$u$$$ ancestor of $$$v$$$), you just have to return $$$dp[v]-dp[parent[u]]$$$. So, by performing a preorder trasversal each subtree becomes a subarray of the euler tour array, so the operations become now: sum $$$x$$$ to all values in a range $$$[l\dots r]$$$ and get the value at some position $$$p$$$; this can be done with Binary Indexed Tree + Difference Array or with Segment Tree + Lazy Propagation (both in $$$O(\log n)$$$ time and $$$O(n)$$$ space).
If I'm not wrong this is what we do in tree flatenning.
yes, that is a way of flatenning the tree. There are other ways with different uses. For example: to query LCA in $$$O(1)$$$ with SparseTable-preprocessing, you can insert each node $$$u$$$ on the array when you visit it by first time and after you finish processing each one of $$$u$$$'s children; let's say $$$pos[u]$$$ is a position of $$$u$$$ on the euler-tour array. then the $$$LCA(u,v)$$$ is the node with lowest level in the subarray $$$[pos[u]\dots pos[v]]$$$.
Another way of doing it is with BFS, so the nodes of same level form a subarray of the built array.
Another way of doing it is with DFS inserting the nodes the first time we visit it and when we goes out of its subtree. This is used to apply Mo's algorithm on trees
Another way is HLD, this is very useful to apply queries and updates over paths on a tree.
Thanks for this knowledge.
Thanks !
try this, this and this
Thanks a lot !
Hey bro I got a good one https://oj.uz/problem/view/APIO13_toll it uses tree flattening.
Thanks !