POJ 1655 Balancing Act(TLE)

gistfile1.cpp

#include <cstdio>
#include <map>
#include <vector>
#include <climits>
using namespace std;
typedef pair<int,int> P;
map<P,int> dp;
vector<vector<int> > edge;
int solve(int from,int to){
    P pa(from,to);
    if(dp.find(pa)!=dp.end()){
        return dp[pa];
    }else{
        int sum=0;
        for(int i=0;i<edge[to].size();i++){
            if(edge[to][i]!=from){
                sum+=solve(to,edge[to][i]);
            }
        }
        return dp[pa]=sum+1;
    }
}
int main(){
    int t;
    scanf("%d",&t);
    for(int ix=0;ix<t;ix++){
        int n;
        scanf("%d",&n);
        printf("%d\n",n);
        edge=vector<vector<int> >(n,vector<int>());
        dp=map<P,int>();
        for(int i=0;i<n-1;i++){
            int fr,to;
            scanf("%d%d",&fr,&to);
            fr--;to--;
            edge[fr].push_back(to);
            edge[to].push_back(fr);
        }
        int mi=INT_MAX,at;
        for(int i=0;i<n;i++){
            int ma=0;
            for(int j=0;j<edge[i].size();j++){
                ma=max(ma,solve(i,edge[i][j]));
            }
            if(ma<mi){
                mi=ma;
                at=i;
            }
        }
        printf("%d %d\n",at+1,mi);
    }
}