lth's blog

Problem on a tree
By lth, 10 years ago, In English

Hi guys.
I am trying to solve the following problem :
Given a tree, you must remove an edge and add an edge so that the new tree is connected and diameter of the new tree is smallest possible. Number of vertices are up to 300000.
When I remove any edge (u,v) I got 2 new trees: one rooted at v and one for which u is leaf. It is obvious that smallest diameter I can achieve is max{d(first tree),d(second tree),d(firs_tree)/2+d(second_tree)/2+1}. Now I can traverse over all edges and remove them and take minimum of those values. Now problem is: I can calculate the diameter of the hanging tree just using dynamic programming on the tree, but I am somehow in trouble of calculating the diameter of the trimmed tree. It seems it is also possible to calculate the diameter of the trimmed tree using dynamic programming but in opposite order, I mean from leaves to root or somehow, but I don't know how exactly to do that. Can anyone help me or give me some hints ?
Thanks in advance.

P.S. Problem is not from currently running contest.

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

»
10 years ago, # |
← Rev. 6   Vote: I like it +8 Vote: I do not like it

Suppose that we want to calculate diameter of some subtree. We can use the following approach.

We can prove that . Where d1 and d2 are fartest vertexes.

So we can create a dynamic data structer which allow us to do two operations :

  • insert a vertex

  • ask for diameter.

We will create an in order travel of the tree where any subtree will denote a interval. After then while removing a edge we can calculate diameter of fixed subtree(the one leaving from the tree). Because it denotes a single interval. Also other part of the tree denotes atmost two interval. Create a segment tree which allows to do above two operations.

Overall complexity is O(NlogN) if we can query lca O(1).(which can be done with RMQ).

PS: I have realized this solution is way too much compilcated comparing to the dynamic programming one but i think it is somehow interesting anyway.

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

    Thank you for your response! To be honest I knew O(NlogN) complexity solution, but in editorial it was mentioned O(n) solution which used idea I mentioned above, I was just wondering how to make reverse order dynamic programming on tree ?

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

      Link to the problem?

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

      Memorize the result of dynamic programming by the pair (v, par). There are about 3N possible pairs.

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

        What you mean by saying pair (v,par) what par does mean? And how can it help me to calculate diameter of the trimmed tree ?

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

          Say, we have standard function dfs(v, par) calculating diameter of the tree rooted in v and given direction par (parent)  →  v  →  children of v.
          To compute desired value one has to take max(dfs(child_v, v), max1 + max2 + 2) there max1 and max2 are the first and the second maximum depth of v's childs.

          Function depth(v, par) works in the similar way.

          So, we only have to calculate dfs(v, par) and depth(v, par) 2 times for every direction of every edge and N times for (v, -1).

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

            Thank you very much, that is what I wanted !

            → Reply