svg_af's blog

Finding two paths in a tree ?
By svg_af, history, 9 years ago, In English

Hello There

I came across this problem on spoj

we're given a tree and we have to find two paths that don't share vertices and which sum of their length is maximum

no i got an idea where we compute the longest path for each subtree rooted with vertex u and there answer is the max sum for each node where for each node we sum the longest path in the subtree rooted with u and the longest path in the entire tree minus the sub tree rooted with u

the latter was a bit confusing for me and i couldn't come up with the solution

any advises or hints about how to compute the longest path in the tree minus the subtree rooted with u for each vertex u would be greatly appreciated

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

»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

http://apps.topcoder.com/forums/?module=Thread&threadID=677305&start=0&mc=11

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

    Yes exactly what i had in mind for computing the longest path in a subtree T`

    but i couldn't really understand what he's doing when he's computing longest path in T/T`

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

      Let dp[u][p] be the length of the longest path in a subtree u, where p is the parent of u. The answer is just dp[u][p] + dp[p][u]. To calculate dp[u][p], you may notice that the longest path must either be in a subtree c (c is a child of u) or goes through u. For the later case, you have to know the longest path in all the subtree c, starting at c.

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

        so if p is parent of u ... answer is longest path in subtree of u + longest path in subtree p/u ?

        how would that be the answer ?

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

          Because the two paths don't share vertices, we can split the tree into two subtrees by cutting an edge. Then the two paths will be in different subtrees.

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

            so p is the direct parent of u ? ... or every ancestor of u ?

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

_and which sum of their length is maximum_

They want two paths don't share vertices and which product of their length is maximum

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

If you are still interested, I wrote a description in quora.

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

    Your solution would probably time out even in C++, as the complexity is O(n2).

    Consider a case in which vertex 1 is connected to all other vertices.

    Edit: Wow, I just took a look at the editorial for that Codeforces contest and the official solution has the same complexity. Indian contests...

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

      you are right, problems with bad tests cases allows this to pass (like the one in codeforces) :P.

      Thanks.

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

      We can keep linear time complexity if before running the described algorithm we binarize the tree, I mean adding dummy nodes to each node with more than two sons, in the worst case, N dummy nodes will be added, also this adds complexity to the code and may never pass SPOJ time limit.

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

        Note that simply binarizing the tree before running the algorithm may change the final answer, which is not what you want.

        You can probably get away with it if you treat dummy nodes and real nodes differently, but then the code gets considerably more complicated, because you're coding two different dfs functions instead of just one.

        Once you've figured out exactly how to make this work, you should probably edit your quora answer to avoid spreading misinformation.

        Edit: I coded what I think you meant by binarization in 16878650. Note that, in the dfs function, nodes with d != 0 are dummy nodes, and are treated differently than nodes with d == 0.

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

          You are right, after binarizing the tree we need to handle 0/1 weights in the nodes (this is the same as the codeforces problem).

          Is not difficult to handle the weights (I did it here 16865336), and the hash table becomes no necessary because the maximum degree of a node is 3.

          I will describe the approach in quora later, and the problem you put is exactly the one in SPOJ with lower constraints.

          I didn't put much attention to your code but is shorter of what I though, thanks.

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

          I have some questions about your logic.

          1- Why you are adding two dummy nodes per node?

          2- What is the logic behind this (I think is related to previous question)?:

                  if (d) {
            p1 = dfs(adj[v][p].first, adj[v][p].second, 0);
            p2 = dfs(v, p+d, d);
        }
        else {
            p1 = dfs(v, p-1, -1);
            p2 = dfs(v, p+1, +1);
        }

          3- And finally, why are you erasing second deepest path length when a node is not dummy?

                  if (!d) {
            ret.longest_path = max(ret.longest_path, ret.deepest_path[0] + ret.deepest_path[1] + 2);
            ret.deepest_path[0]++; ret.deepest_path[1] = -1;
        }
          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            I actually think it would be much easier for you to write your own code if you have the idea, and it shouldn't be hard to make something clearer than what I did. In fact the answer to most of these questions is "because it was the first way I thought to code it".

            For question 3, it's because you can't have a path go through the path between a parent and a child more than once.

            For questions 1 and 2, I add two dummies for every edge (one in each direction). So if 1 connects to 2, 3, and 4, I'll have in the resulting tree:

              1
  |
dummy -- dummy -- dummy
  |        |        |
  2        3        4

            So you can see the dummies form a line, d=-1 means we're coming from the right dummy, d=1 means we're coming from the left dummy.

            Perhaps it's easier to say that each dummy represents a prefix (if d=-1) or suffix (if d=1) of the children of 1.

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

              I did my own implementation and seems that I'm missing a corner case.

              My logic is as follows: For each node having degree > 3 (parent and two sons) I add 1 dummy node, after this the node will have at most 3 links.

              for a tree like this:

              1-------
| \  \  \
2  3  4  5

              I will have this:

              1-----
|  \  \
2   3  dummy--4
         \----5

              For each dummy node I compute the two deepest levels, this because a dummy node represents more than 1 son for the real node.

              The longest path in a dummy node can include it only including the deepest level through the dummy author (the node that required to create this dummy node) and other deepest level (if exists).

              I did several tests and is failing with bigger tests (non manually debugable).

              Do you think my logic makes sense? Maybe I made a mistake in the implementation.

              Thanks for your previous details.

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

                I don't understand, sorry... What is this supposed to mean? "The longest path in a dummy node can include it only including the deepest level through the dummy author (the node that required to create this dummy node) and other deepest level (if exists)."

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

                  While creating a link(u, v) if degree(u) == 2 I add a dummy node to u to keep its degree in exactly 3, some like: u -> dummy1 -> v, in this case I say that dummy1 was created by u.

                  Suppose we have this tree (test 23)
                  This is the modified tree

                  Nodes with label > 15 are dummy nodes. The following table shows the author of each dummy node:

                  dummy | author
 16   |  12
 17   |  15
 18   |  17
 19   |  16
 20   |  19
 21   |  18

                  Removing edge(15, 16) we have a path with length 4 starting at 15 (from 6 to 11), and a path of length 4 starting at 16, note that 16 is dummy and was created by 12, so the the we can use the path from 1 to 2.

                  Removing edge(12, 16) we can compute the longest path including 16 and it can be this (removing dummy nodes): 2, 7, 15, 6, 14. Which is not possible, see the original tree and edge(7, 15) doesn't exists, to reach 15 from 7 we need 12 which is the author of dummy node 16.

                  I submitted the code here: 16980218

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

                  I won't go into the code since it's very big, but a possible corner case is what happens when 2 dummy nodes connect.

                  When you cut edge(15,16), will you consider the path 13-19-20-7-2? It is a valid path (even though it doesn't go through 12).

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

                  Not really, author(19) = 16, so the path I will consider is deepestLevel(19), while doing dfs(19, 16) edge(19, 16) is cut, so the author of 19 is not reachable and I will consider only deepestLevel(19, 16) which is 2 (19, 20, 7, 2).

                  There should be a case I'm missing but I had no found it yet.

                  If a node is dummy, there are two cases:

                  1. author(node) is not reachable, so I consider only the deepest level.
2. otherwise I consider the path with deepest level from author + deepest level no from author.

                  Thanks.

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

                  As I said, 13-2 is a valid path, so if your code doesn't consider it for whatever reason the code is wrong.

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

Here is what I think (it might be wrong...) disconnect each edge of tree one by one...when u disconnect one edge u will get 2 trees...find diameter of each of tree and update answer to maximum of answer and sum of the 2 diameters...

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

I think 633F - The Chocolate Spree is almost same problem. It can be solved by tough tree dp but thinking how to merge data carefully lead me to correct solution. See 16678710.

→ Reply