#include <bits/stdc++.h>
using namespace std;
template
class Graph
{
map<T,list<pair<T,int> > > adj;
int v;
public:
Graph(int x)
{
v=x;
}
void addEdge(T x,T y, int weight)
{
adj[x].push_back(make_pair(y,weight));
adj[y].push_back(make_pair(x,weight));
}
void print()
{
for(auto it1=adj.begin();it1!=adj.end();it1++)
{
T node = it1->first;
cout<<node<<" : “;
for(auto it2=adj[node].begin();it2!=adj[node].end();it2++)
{
cout<<”("<first<<","<second<<")->";
}
cout<<“X”<<endl;
}
}
pair<int,int> func(int node,map<int,bool> visited)
{
visited[node]=true;
int count=0;
int cost=0;
for(auto it=adj[node].begin();it!=adj[node].end();it++)
{
if(visited[it->first]!=true)
{
pair<int,int> p=func(it->first,visited);
count=p.first+count;
cost=cost+2min(p.first,v-(p.first))(it->second)+p.second;
}
}
return make_pair(1+count,cost);
}
pair<int,int> func_helper()
{
map<int,bool> visited;
for(auto it=adj.begin();it!=adj.end();it++)
visited[it->first]=false;
return func(adj.begin()->first,visited);
}
};
main()
{
int t;
cin>>t;
int i=1;
while(t–)
{
int n;
cin>>n;
Graph<int> g(n);
for(int i=1;i<n;i++)
{
int x,y,w;
cin>>x>>y>>w;
g.addEdge(x,y,w);
}
// g.print();
pair<int,int> p=g.func_helper();
cout<<"Case #"<<i<<": "<<p.second<<endl;
i++;
}
}
This is showing TLE, can I have a better approach ??