benefact_bfs.cpp

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

// Useful constants
#define INF                         (int)1e9

typedef pair<int, int> pii;
vector<vector<pii>> graph;
vector<bool> visited;
vector<int> dist;

#define pb push_back

int bfs(int src)
{
    queue<pii> q;
    pii s;
    int sid, sw, id, w;

    for (int i = 0; i < 50005; i ++) {
        visited[i] = false;
        dist[i] = 0;
    }

    visited[src] = true;
    s =  pii(0, src);
    q.push(s);

    while (!q.empty())
    {
        s = q.front(); q.pop();
        tie(sw, sid) = s;

        for (auto &i : graph[sid])
        {
            std::tie(w, id) = i;

            if (!visited[id])
            {
                q.push(i);
                visited[id] = true;
                dist[id] = dist[sid] + w;
            }
        }
    }

    return distance(dist.begin(), max_element(dist.begin(), dist.end()));
}

int main()
{
    int T, n, a, b, w;
    string line;

    graph = vector<vector<pii>>(50005 , vector<pii>());
    dist = vector<int>(50005, 0);
    visited = vector<bool>(50005, false);

    cin >> T;
    while (T--) {
        for (int i = 0; i < 50005; i++)
            graph[i].clear();
        cin >> n;
        n--;
        while (n--) {
            cin >> a >> b >> w;
            graph[a].pb(pii(w, b));
            graph[b].pb(pii(w, a));
        }

        a = bfs(1);
        b = bfs(a);
        cout << dist[b] << endl;
    }

    return 0;
}