SRM635 Div2Hard LonglongestPathTree

#include <bits/stdc++.h>

using namespace std;
  
// rep
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
  
struct Edge
{
  int to, cost;
};

// typedef
typedef vector<Edge> Edges;

typedef long long ll;

int N;
Edges G[2010];
bool notuse[2010];

typedef ll Weight;
typedef pair<Weight, int> Restype;

class LonglongestPathTree {
public:
  
  Restype dfs(int p, int v) {
    Restype r(0LL, v);
    rep(i, G[v].size()) {
      Edge &e = G[v][i];
      if(notuse[v] && notuse[e.to]) continue;
      if(e.to != p) {
        Restype t = dfs(v, e.to);
        t.first += e.cost;
        if(r.first < t.first) r = t;
      }
    }
    return r;
  }
  
  Weight diameter(int s) {
    Restype r = dfs(-1, s);
    Restype t = dfs(-1, r.second);
    return t.first;
  }
  
  ll getLength(vector <int> A, vector <int> B, vector <int> L) {
    
    ll N = A.size();
    rep(i, 2010) G[i].clear();
    rep(i, N) {
      G[A[i]].push_back((Edge){B[i], L[i]});
      G[B[i]].push_back((Edge){A[i], L[i]});
    }

    ll mx = diameter(0);
    rep(i, N) {
      notuse[A[i]] = notuse[B[i]] = 1;
      mx = max(mx, diameter(A[i])+diameter(B[i]) + L[i]);
      notuse[A[i]] = notuse[B[i]] = 0;
    }
    
    return mx;
  }
};