radoslav11's blog

Question about AtCoder Grand Contest 18 Problem D.
By radoslav11, history, 7 years ago, In English

Hello.

Today I was looking the problems from AtCoder Grand Contest 18. In problem D you were asked to find the length of the largest Hamilton Path in a complete graph with edges between two vertices equal to the length between these two vertices in a given tree. In the problem you need to find just the length of the path and the solution which I found to the problem can do this. But unfortunately it can just give the length of the path, not the order in which we visit the vertices (my solution is similar to the one in the editorial). So is there a solution with which the order we visit the vertices is easily recoverable (well actually even if it's not easy I would appreciate if you share your idea) and also is still fast enough (something like or faster).

Thanks in advance :)

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

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

Auto comment: topic has been updated by radoslav11 (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

after rooting at the centroid , the order of visiting nodes pretty much doesn't matter as long as two consecutive nodes are from different subtrees of the root , so at each step , choose a node from largest subtree which is different from the last node chosen.

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

    Thanks. I also had that idea but I don't know why I thought that after we have chosen some nodes it would be possible that some paths won't go through the centroid but obviously if we choose the largest subtree that will never happen. Thanks again.

    → Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

This might be useful

→ Reply