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?
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3442 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 166 |
2 | atcoder_official | 163 |
3 | Um_nik | 162 |
3 | maomao90 | 162 |
5 | adamant | 157 |
5 | djm03178 | 157 |
5 | -is-this-fft- | 157 |
8 | awoo | 155 |
9 | TheScrasse | 154 |
10 | Dominater069 | 153 |
Intuition behind "CSES — Network Renovation"
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?
Name |
---|