can anyone help me out in the below problem solution. I didn't understand the editorial. https://codeforces.com/contest/1286/problem/B

Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3404 |

3 | TLE | 3356 |

4 | apiadu | 3351 |

5 | mnbvmar | 3281 |

6 | LHiC | 3276 |

7 | Um_nik | 3268 |

8 | 300iq | 3267 |

9 | yosupo | 3249 |

10 | ainta | 3226 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 190 |

2 | antontrygubO_o | 186 |

3 | tourist | 182 |

4 | Radewoosh | 169 |

5 | vovuh | 167 |

6 | pikmike | 166 |

7 | ko_osaga | 161 |

8 | Um_nik | 160 |

9 | Petr | 155 |

10 | McDic | 153 |

can anyone help me out in the below problem solution. I didn't understand the editorial. https://codeforces.com/contest/1286/problem/B

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/19/2020 23:50:15 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

:)