Pの競プロ記

競技プログラミングに関することを書きます。

ARC #022 C ロミオとジュリエット

概要


問題文はこちら
http://arc022.contest.atcoder.jp/tasks/arc022_3

コンテスト中に満点解法で解くことが出来なかった。

解法


木の直径を求めることでこの問題を解くことができます。

やり方はとても簡単でDFSを2回やればよいです。具体的なやり方は以下の通りです。
・どこでもよいので適当な頂点を1つ選びそこから最も遠い頂点xを選ぶ
・今度は頂点xから一番遠い頂点yを選ぶ
・頂点x、yは木の直径となる

ちなみにここにちゃんとしたやり方が載っています。

とてもシンプルな考え方なのでぜひ覚えておきたい。

ソースコード

#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cctype>
#include <cassert>
#include <cstring>

using namespace std;

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back

typedef pair<int,int> P;
typedef long long int lli;

const int INF = (1 << 30);
const double EPS = 1e-9;
const double PI = acos(-1.0);

int N;
vector<int> edge[100000];
bool visited[100000];

P dfs(int v) {
  visited[v] = true;
  
  P res = P(0, v);

  rep(i, edge[v].size()) {
    if(visited[edge[v][i]]) continue;
    P tmp = dfs(edge[v][i]);
    tmp.F++;
    if(res.F < tmp.F) res = tmp;
  }

  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  
  cin >> N;
  N--;
  rep(i, N) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    edge[a].pb(b);
    edge[b].pb(a);
  }

  memset(visited, false, sizeof(visited));
  int A = dfs(0).S;
  memset(visited, false, sizeof(visited));
  int B = dfs(A).S;

  cout << A + 1 << ' ' << B + 1 << endl;
  
  return 0;
}