Tamflexの貯蔵庫

やる気のない備忘録

codingame - Teads Sponsored Contest

グラフの直径を求めれば良い
以下が参考になる
Spaghetti Source - 木の直径

前に解いたabc019のdouble sweepのアルゴリズムを思い出した.
計算量はO(E)
この手の問題は多いのでそのうちグラフをクラス化して保存しておきたい.
直径,最小全域木等をg.diameter()みたいに呼び出せるとカッコイイかも

template<typename T>
struct Edge
{
  int dst; T w;
  Edge() {};
  Edge(int dst): dst(dst) {w=1;};
  Edge(int dst, T w): dst(dst), w(w) {};
  bool operator < (const Edge &e){return w != e.w ? w > e.w : dst < e.dst;}
};

typedef vector<Edge<ll>> Edges;
typedef vector<Edges> Graph;

/*
int p cost
int v distnation
Graph &g graph
頂点vから最も遠い点の距離とその点の番号を返す
if(p==-1) vがroot
*/
pair<ll,int> visit(int p, int v, const Graph& g)
{
  pair<ll,int> r(0,v);
  for(auto e : g[v]) if(e.dst != p)
  {
    auto t = visit(v,e.dst,g);
    t.first += e.w;
    if(t.first > r.first) r=t;
  }
  return r;
}

ll diameter(const Graph& g)
{
  auto r = visit(-1,0,g);
  auto t = visit(-1,r.second,g);
  return t.first;
}

int main()
{
  int n; cin >> n;
  Graph g(n*2+1,Edges(0,Edge<ll>()));
  REP(i,n)
  {
    int s,t; cin >> s >> t;
    cin.ignore();
    g[s].push_back(Edge<ll>(t));
    g[t].push_back(Edge<ll>(s));
  }
  ll a=diameter(g);
  cout << (a%2?a/2+1:a/2) << endl;
}