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

my code :http://www.ideone.com/k2mF5

GOT AC!!!

THANKS ALL.

Let's name longest path in a tree - diametr. How to find it?!

We can find it by using DFS/BFS.

First, let's run bfs from any vertex. After, take the further vertex, and denote it as

u.Then, run bfs from

u, and find the further vertex from it, and denote it asv.Diametr is distance between

uandv.So, complexity is

O(V+E)Look, you used array

N*N. It takes a lot of memory and etc.I do not use java, but in C++, you can use vector<vector <int> >.

Here

N≤ 10^{4}. It is small value. If you optimise your code, I think you will get AC.try it and solve your problem you can do and take help from specialist ..............................

Hello you are welcome to CODE FORCES Howsoever long the path may be, you can always rely on Long Path Tool. Its sure to sort out your problem.

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.

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 -

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 !

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:

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

@Akul — Thanks for pointing out the bug. But, as you said, the Logic is yet to be verified.

Why don't you just find the diameter of the tree??

@trophies — I have successfully implemented that approach, but I to set in the intuition right, I wanted to think of the other possibilities/approaches. After all, the real learning is when we try to think of alternative and multiple approaches. The purpose was not just to get to the answer.

how to find the longest path using dfs?

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