horseprabhat625's blog

Number on tree problem
By horseprabhat625, history, 5 years ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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

        → Reply