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

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

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!

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

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

    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 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.