Moving Through Trees

Well this week has been pretty successful so far. I've managed to solve 4 SPOJ problems I think, though one was just applying a "basic" geometry formula.

Of the remaining problems the first was about playing a game optimally. Usually I detest doing these kinds of problems, but once I noticed that there were solutions in Brainf**k I knew that there was something I was missing. Here is the link to the problem, as far as hints go all I will say is play the game by hand for the first few (under 30) numbers and you should notice a pattern.

The next two problems are pretty similar. Since I am going be describing how I actually solved them I will not be providing a link. They were both asking you to find the longest path within a given tree. The naive approach (and probably more difficult to program) approach would be to find the distance between very possible pair of vertices. This is going to result in an O(n^2) algorithm, and not to mention that it isn't immediately obvious how to find the distance between two given vertices. Naturally the next I idea was to use a depth first or breath first search, the issue now becomes knowing if you have found the longest path. Well here is the approach that I used; start with any vertex of the tree and then use DFS (depth first search) to find the vertex that is farthest from it, call this vertex X1. Now do another DFS starting with X1 and find the vertex X2 that it is furthers from. The distance between X1 and X2 will be the longest path in the tree (though I don't feel like proving rigerously or even using hand waving to explain why).

Here is a sample of the code I used to solve the case where all the paths had the same length. It isn't too difficult to modify for weighted trees.

pair< int,int > dfs(vector< int > >&G,int v)
{
   stack< int > S;
   S.push(v);
   vector< int > visit(G.size(),0);
   while(!S.empty())
   {
      int parent=S.top();
      S.pop();
      tr(G[parent],i)
      {
         if(visit[*i]==0)
         {
            S.push(*i);
            visit[*i]=visit[parent]+1;
         }
      }
    }
    vector< int >::iterator    i=max_element(visit.begin(),visit.end());
   return make_pair(i-visit.begin(),*i);
}

The first entry of the returned pair is the vertex farthest from the starting point, while the second entry is the distance. Thus you will run the DFS two times as previously mentioned. So the complexity of this method is O(n) which is much better than the other approach.
It should be noted that the following is at the beginning of the code

#define tr(a,i) for(typeof(a.begin()) i=a.begin();i!=a.end();++i)