Блог пользователя horseprabhat625

Автор horseprabhat625, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    can u explain how to merge the children permutation with the parent one

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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