can anyone help me out in the below problem solution. I didn't understand the editorial. https://mirror.codeforces.com/contest/1286/problem/B
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
can anyone help me out in the below problem solution. I didn't understand the editorial. https://mirror.codeforces.com/contest/1286/problem/B
Название |
---|
i dont read the editorial but my solution was that if in the tree a node like v has sz[v] nodes in its subtree if(sz[v] < a[v]) its impossible to reach the goal. else you can give the weights of its subtree nodes a permutation then for a new vertex you can merge its children permutation to make bigger permutation and then for the root you can actully give the nodes the last permutation if you want you can see my soloution in my submissions
can u explain how to merge the children permutation with the parent one
you have the permutation of the children. for example the node v has 3 children with permutation 123, 12, 1234 : so you merge them and get the 123 45 6789 (you make the permutation of its children from 1 -> x : k -> x + k) and then you have the value of its children and you know where you have to put the v value for example if a[v] == 4 : the permutation become 123 4 5 678910 you add the v's value in the permutation
Thanks i did it with a little different update i,e at every time each node get a unused smallest number then i insert parent in the sorted oreder of permutation of childrens and finally increment the list after the position of parent by one . Got AC
:)