| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
You're given a rooted tree with N nodes and Q queries in each query you have an integer K and you want to delete the nodes of the tree the only restriction of deleting some node is that it must be either the root or its parent must be deleted and you can delete at most K nodes each second, what is the minimum time for deleting all nodes?
N <= 10^6 Q <= 10^6
Reverse time — you can cut only leaves.
Some technical arguments shows that you should cut k leaves with largest depths. After some math you can get result that answer is equal to
, where s(h) is number of leaves on depth h. That is a trivial lower bound, to prove it is also upper bound is what is nontrivial. From that you can get some disguised geometrical interpretation with hull.
(Not sure why, but CF seems to have hard time showing that formula in latex, here it is: max_{l} (l + \lceil \frac{\sum_{h > l} s(h)}{k} \rceil)
How do you prove that cutting leaves with largest depths is optimal?
In fact that is not the exactly the statement we want to prove ;p. What is important is that bound, so focus on proving that one. Right now I don't feel like delving into details of that problem, I gave you right direction ;p.
Can you pleas upload the formula img on a different site
Can't you do it by yourself? You already have the correctly formatted formula. Or parse it with your eyes, it's really easy.