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

Graph problem (spoj) length of the longest path in a tree
Автор matavanga, 13 лет назад, По-английски

i am trying to solve http://www.spoj.pl/problems/PT07Z/  problem.

i first got the most farthest point from root and then got the farthest point from that point
but i am getting TLE. can you please find the appropriate algorithm for this problem .
thanks




GOT AC!!! 
THANKS ALL.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
If you want to stick to this approach, just replace Dijkstra with BFS.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    i tried but that also gives TLE .
    thanks

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Also I'd suggest that you replace "t=Integer.parseInt(lst[ind].get(i).toString());" with something more reasonable. It looks much like "if (booleanVar.toString().length()==4) {...}".
      → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

щи

→ Ответить
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
plz use pastebin.com to post ur code
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
heights for the two largest in the tree, that is, the two leaves below you can find and the result is the sum of both heights
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Use just DP, using simple dfs you can calculate the two deepest nodes and returning the depths of his father, so that it can calculate where the maximum path length in one of its ends to the parent of the node.
→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I also have a problem with this task. My code ( http://ideone.com/RhhwIC ) is getting WA, but I can't find a bad test case. I'm doing DFS to compute paths for all neighbours for all nodes (as a root) and for every node I join two biggest results.

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I have another inefficient approach for solving this problem. The approach would give TLE, but I want to confirm its validity. Please if you could confirm -

START -

1. Make a list of nodes of the Tree storing the "Degree" of each node along with the neighbors of the node. 

2.Initialize Length=0;

3. While there are nodes present in the tree, perform the following
   a. remove the nodes having degree 1. 

   b. if(number of nodes removed >2 ) length+=2 else length+=1

   c. update degree of node and its neighbors

return length

END.

So, here, what I am essentially doing is tapering down the longest path, starting from all the boundary(degree 1) nodes. Is the solution valid?

Thanks in advance !

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Your approach will yield a wrong answer on the following case:

    1---2---3---4

    In the first step you will remove 1 and 4 and update your length to 1. In the next step you will remove 2 and 3 and update length to 2. But as you can clearly see the longest path is from 1 to 4 of length 3.

    Changing your condition to (nodes removed>=2) will also yield a wrong answer in this case. But I think maybe changing your condition to (nodes removed >= 2) and also adding the case that:

    if(nodes left ==2) length++; return length;

    might give you the right answer. No guarantees on that though.

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

how to find the longest path using dfs?

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

    Use two dfs . Firstly choose an arbitrary node a and find the farthest node b from a using dfs. Then find the farthest node c from b using dfs. The distance between b and c will the answer. Link for my code

    → Ответить