EAGLE1 - Eagle and Dogs

#include <bits/stdc++.h>
using namespace std;

const int64_t INF = 0x3f3f3f3f3f3f3f3fLL;

int n;
vector<vector<pair<int, int64_t>>> gr;

pair<int64_t, int> dfs(int u, int64_t w, int par = -1) {
  auto res = pair<int64_t, int>({w, u});
  for (auto [to, d] : gr[u]) if (to != par) {
    auto aux = dfs(to, w + d, u);
    res = max(res, aux);
  }
  return res;
}

void dfs2(int u, vector<int64_t> &dist, int par = -1) {
  for (auto [to, d] : gr[u]) if (to != par) {
    dist[to] = dist[u] + d;
    dfs2(to, dist, u);
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int tc; cin >> tc;
  while (tc--) {
    cin >> n;

    gr.assign(n, vector<pair<int, int64_t>>());

    for (int i = 0; i < n-1; ++i) {
      int a, b, d; cin >> a >> b >> d, --a, --b;
      gr[a].push_back({b, d});
      gr[b].push_back({a, d});
    }

    auto [w, u] = dfs(0, 0, -1);
    auto [ww, v] = dfs(u, 0, -1);
    // cout << 1+u << " - " << 1+v << " = " << ww << '\n';

    vector<int64_t> d1(n, INF);
    vector<int64_t> d2(n, INF);

    d1[u] = 0;
    dfs2(u, d1, -1);
    d2[v] = 0;
    dfs2(v, d2, -1);

    for (int i = 0; i < n; ++i) {
      if (i == u) {
        cout << ww << " \n"[i==n-1];
      } else if (i == v) {
        cout << ww << " \n"[i==n-1];
      } else {
        cout << max(d1[i], d2[i]) << " \n"[i==n-1];
      }
    }
  }
}