--- old.cpp 2015-01-27 11:21:37.440703996 +0100
+++ new.cpp 2015-01-27 11:20:03.427223463 +0100
@@ -79,8 +79,9 @@
    }
 }

+map<tuple<int,int,int>, int> mem;

-int recur( int val , int lastid , int root , vector < int > y )
+int recur( int val , int lastid , int root , const vector<int> &y )
 {
    if ( val == 0 ) return 0 ;

@@ -89,14 +90,16 @@
    if ( lastid  == y.size())
        return ans ;

+   auto key = make_tuple(val,lastid,root);
+   if (mem.find(key) != mem.end())
+       return mem[key];

    for ( int  k1 = 0 ; k1 <= val ; k1++)
    {
        ans = min ( ans , dp[y[lastid]][k1] + recur ( val - k1 , lastid + 1 , root , y ) ) ;
    }

-
-   return ans ;
+   return mem[key] = ans;

 }

@@ -124,6 +127,7 @@

    //case 1

+   mem.clear();
    if ( present[root])
    {   for ( int j = 2 ; j <= k ; j++)