#include <bits/stdc++.h>
using namespace std;
#define ll long long
class Graph
{
ll V;
list<pair<ll, ll>> *l;
public:
Graph(ll v)
{
V = v;
l = new list<pair<ll, ll>>[v];
}
void addEdge(ll u, ll v, ll cost)
{
l[u].push_back(make_pair(v, cost));
l[v].push_back(make_pair(u, cost));
}
ll dfshelper(ll node, bool *visited, ll *count, ll &ans)
{
visited[node] = true;
count[node] = 1;
for (auto nbr_pair : l[node])
{
ll nbr = nbr_pair.first;
ll wt = nbr_pair.second;
if (!visited[nbr])
{
count[node] += dfshelper(nbr, visited, count, ans);
ll nx = count[nbr];
ll ny = V - nx;
ans += 2 * min(nx, ny) * wt;
}
}
return count[node];
}
int dfs()
{
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
ll *count = new ll[V];
for (int i = 0; i < V; i++)
count[i] = 0;
ll ans = 0;
dfshelper(0, visited, count, ans);
return ans;
}
};
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin >> t;
for (ll tt = 0; tt < t; tt++)
{
ll n;
cin >> n;
Graph g(n);
ll x, y, z;
for (ll i = 0; i < n - 1; i++)
{
cin >> x >> y >> z;
x--;
y--;
g.addEdge(x, y, z);
}
cout << "Case #" << tt + 1 << ":"
<< " " << g.dfs() << endl;
}
}
it’s showing wrong when submitted on spoj, what is the mistake?