antivenom's blog

Help needed in an Interesting Graph problem
By antivenom, 9 years ago, In English

So question is something like this- "We are given a tree(weighted) and we have to find longest path in the tree and number of all such possible paths ".Number of nodes is of order (<=10^4).

If I am not wrong part 1 can be done using two dfs(please point me if it is wrong).For the second parth I thought it must be some dynamic programming but could not get to any solution.Help me to find "How many such possible path(with longest distance) exist in the tree" ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Yes, it could be done using two DFS. But for the second question do you mean the number of paths which has a length equal to the longest path or the number of paths in general?

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

    Yes!!! I mean-"total number paths having the longest length in the tree".

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

      n=?

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

        Mate if I think you want constraint for number of nodes.It is (n<=10^4)

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

          With n <=10^4 it can be done using the same method for solving this problem 161D - Расстояние в дереве but since you are counting the number of longest paths in a tree I remeber that someone told me that there is a O (n) solution but I don't know it :(

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

          But this DP solution here is not suitable since it can be solved with same complexity but with bruteforce

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

nojefndlamefneqldmqefnqelfd;m

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

if weights greater that zero any longest path should contain at least one node from first one (it can be found by two dfs).

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

Let's select node #1 as a root and hang the tree from it, so that every other node will get a parent. Now for every node we can calculate the distance to its farthest descendant (which of course will be a leaf), let's call it a height of current node. And also we will calculate the number of such leafs providing max height for current node.

For all leafs the height will be 0 and the count will be 1 (empty path containing only the leaf itself). For any other node, if we have already calculated heights for its childs then for current node the height can be calculated using heights of all childs and edge weights connecting them to current node.

After that we will be able to calculate the number of longest paths which contain current node and fully belong to its subtree. To do that we will take two childs providing max heights for current node connect them through it. It is possible to calculate the number of such paths in O(N * logN) by sorting children and multiplying their quantities by the sum of quantities of other childs which provide the max answer when paired with the current one. If current node has only one child, then we will just take the max height of that child and add the edge weight connecting it to current node.

→ Reply