木の直径を求める

グラフG(V, E)について考える。G(V, E)の頂点間距離の最大値をG(V, E)の直径と呼ぶ。
木の直径はDFSを2回行うことで簡単に計算できる。

AOJに木の直径を求める問題があったので、解いてみた。

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define ALL(x) (x).begin(), (x).end()

vector<pair<int, int> > g[100000];

pair<int, int> tddfs(int v, int par = -1) {
  pair<int, int> ret = {0, v};
  for (auto &x : g[v]) {
    int w, cost;
    tie(w, cost) = x;
    if (w == par)
      continue;
    auto r = tddfs(w, v);
    ret = max(ret,  {cost+r.first, r.second});
  }
  return ret;
}

int treeDiameter() {
  auto v = tddfs(0);
  auto w = tddfs(v.second);
  return w.first;
}

int main() {
  int n;
  scanf(" %d", &n);
  REP (i, n-1) {
    int x, y, d;
    scanf(" %d %d %d", &x, &y, &d);
    g[x].push_back({y, d});
    g[y].push_back({x, d});
  }
  int ret = treeDiameter();
  printf("%d\n", ret);
  
  return 0;
}