Hello,
could anyone please explain me the intuition behind the solution of CSES-Network Renovation?
The solution to the task
Why does this greedy strategy suffice for connecting the entire tree?
№ | Пользователь | Рейтинг |
---|---|---|
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 | 160 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | nor | 153 |
9 | Dominater069 | 153 |
Hello,
could anyone please explain me the intuition behind the solution of CSES-Network Renovation?
The leaves of the tree have to be connected to each other, because if a leaf isn't connected with an additional edge to another one, the "parent edge" might just break down and in that case, it's not possible to leave this leaf.
Suppose that we have k
leaves. After sorting the leaves in DFS-Order, connect each leaf i
with a leaf that has the index i + (k/2)
.
Why does this greedy strategy suffice for connecting the entire tree?
Название |
---|
You can understand the intuition of the solution in intuition.
The gist of it is by adding k/2 we are guaranteed to have the nodes belong to different subtrees.
Hope this helps.