（コスト付き）木の直径(by dfs) 復元付き

ライブラリ 
// 木の直径（コストあり）
struct TreeDiameter{
  vector<vector<PII>> G; // (to, cost)
  ll N;
  ll start,end;
  VI path;
  ll d;
  VI TO;
  // 初期化のみ
  TreeDiameter(ll n){
    N=n;
    G.resize(N);
    TO.resize(N, -1);
  }
  // 辺登録 (両方向!!)
  void add_edge(ll a, ll b, ll cost){
    G[a].push_back({b,cost});
    G[b].push_back({a,cost});
  }

  // 直径を計算。値はdに入る
  void calc(){
    auto pa = dfs(0, -1);
    ll farthest_index = pa.second;
    pa = dfs(farthest_index, -1);
    // 結果
    d = pa.first;
    start=farthest_index;
    end=pa.second;
  }
  // 最長距離とその頂点indexを返す
  PII dfs(ll i, ll prev){
    PII ret = {0,i};
    for(auto pa : G[i]){
      ll to = pa.first;
      ll cost = pa.second;
      if(to==prev)continue;
      auto result = dfs(to, i);
      // より遠くへ行ける方向を見つけた
      if(result.first + cost > ret.first){
        ret.first = result.first + cost;
        ret.second = result.second;
        TO[i]=to;
      }
    }
    return ret;
  }
  VI get_path(){
    VI V;
    V.push_back(start);
    ll now=start;
    while(now!=end){
      ll to = TO[now];
      V.push_back(to);
      now = to;
    }
    return V;
  }
};

他の問題もACしておく