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

Автор go_rob, история, 8 лет назад, По-английски

Given a binary tree,

We have to remove a single edge and partition the tree into two new trees such that difference of their diameters remains less than a given constant k.

Please suggest me an approach of O(n) time complexity.

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

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

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

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

one way is to store the three longest paths starting at each vertex (note that each path should go through a distinct vertex), this can be done in O(N) and having this information you could easily choose an edge to remove and compute the diameter of each tree.

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

I found a method but I don't think it is the best approach. It seems too messy for my taste — I would like to hear any better solutions!

Spoiler
»
8 лет назад, # |
Rev. 4   Проголосовать: нравится +15 Проголосовать: не нравится

I am not sure about my solution, but looks reasonable to me.

----------------------spoiler-------------------------

so say u have a binary tree looks like

let f[i] represent the longest distance from i to any vertex in the subtree of i.

it is easy to get in o(n).

so consider we are deleting the edge from x to its father. (in the figure we assume x = 2)

therefore the tree is split into two parts, rooted by 2 and 1.

for 2, the diameter = f[lson]+f[rson]+1 (coz it is binary tree)

for 1, the diameter = f[rson]+1

so u can just bruteforce the deleted edge, and calculate the difference.

I think it is reasonable for me, but if there is something wrong or bug, please point it out, thanks a lot.

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

    Your solution seems buggy.

    The two Eqn for the diameter that you have written doesn't hold true for many cases.

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

      ah sorry i misread the problem,

      so like, u make dp[i] to the diameter of the tree rooted by i.

      the same thing, then for 2, it looks like dp[2] straightly. for 1, it is max(dp[rson], f[rson]+1)

      is it work? sorry for the retarded previous answer :L

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

        I don't think your solution will work in all cases. The max(dp[rson], f[rson] + 1) will not not always work.

        I am providing a better solution here

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

Guys, I have found out a solution using DP which will work in O(n) using 2 DFS. Here is the code, Please check the code and verify its correctness.