I was trying to solve this problem on Codechef . Click Here
After spending a couple of hours on this I could not come up with any dp relation .
Can someone please provide a dp recurrence for this problem and help me solve it ?
Thanks in advance.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
I was trying to solve this problem on Codechef . Click Here
After spending a couple of hours on this I could not come up with any dp relation .
Can someone please provide a dp recurrence for this problem and help me solve it ?
Thanks in advance.
Название |
---|
Break free can be solved using binary search and greedy. Let us binary search on the answer, now we have to find minimum number of edges to be broken to decrease all subtree sizes to less than X. The greedy idea is to DFS the tree, and whenever a sub tree has greater than X weight, remove the edge to the heaviest children. It is easy to see why this works. Complexity is where S = max sum of tree weights(2·1013).