TheOpChicken123's blog

By TheOpChicken123, history, 2 years ago, In English

Hey all, I have been struggling with this question for quite a while now (almost three months) and there are no solutions that I can find online. It is from the Singaporean NOI qualification 2022 qualification test. The problem is described in the title —

given a tree, find the maximum diameter of the tree if you can remove one edge, and put that edge anywhere else. However, in the end, it must remain a tree. This is the link to the problem which also contains two testcases. https://codebreaker.xyz/problem/treecutting

I have been able to do it in O(n*n) by brute force but it is too slow. Can anyone help? Any help will be greatly appreciated. Thank you!

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
2 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it
1
2
3
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hello, thank you so much for your help. I understand part 1 and part 2 and half of part 3 — when I am ocmputing all D(u, v) and F(u, v) where T(u, v) contains r. But what I am not sure about is how do i compute D(v, u) and F(v, u) where T(v, u) contains r? My previous solution was also O(n*n) because I had previously realised 1, and 2, but did not know how to compute all D(u, v) and D(v, u) efficiently.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it +13 Vote: I do not like it

      Suppose you've computed the values for the first phase.

      When you're on node $$$u$$$, you just remember

      1. the largest value $$$L_{D1}$$$ and

      2. the second largest value $$$L_{D2}$$$, which possibly is equal to $$$L_{D1}$$$,

      among $$$D(v, u)$$$ for all neighbors $$$v$$$ of $$$u$$$. Similarly, you remember

      1. the largest value $$$L_{F1}$$$,

      2. the second largest value $$$L_{F2}$$$, and

      3. the third largest value $$$L_{F3}$$$.

      among $$$F(v, u) + 1$$$ for all neighbors $$$v$$$ of $$$u$$$.

      Then for all child $$$w$$$ of $$$u$$$, $$$D(u, w)$$$ is formed by either choosing one $$$D(u, v)$$$ or by attaching two $$$F(u, v) + 1$$$. You just greedily pick the largest of the values remembered as long as they're not equal. Same for $$$F(u, w)$$$.

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

You have to find for all nodes, the diameter of the tree rooted at this nodes subtree and the diameter of the tree formed by removing this node's subtree. Answer is max of sum ov these values over all nodes. You can do this using a dfs.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I am aware of that, but I am just not sure how to do this efficiently. Do you think you could help me with the specific algorithm? I don't have a lot of experience with this. Thanks!

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

      Do you have access to submissions? I can send you my code and if the implementation is correct then I can explain it too

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

        Yes I do, if you create an account to the website i linked in my original post you can submit your code there. But if you want I can submit and test it for you as well.