AtCoder Regular Contest 022 C - ロミオとジュリエット

問題

　頂点の木が与えられるので最も距離が長くなるような2つのノードのペアを一つ答えよ。

解法

　ある頂点を根として考え、そこから再帰関数を回す。それぞれの関数内では、そのノードから各リーフノードへの距離と、リーフノードの番号を返すようにする。一つ上のノードは隣接ノードについてこの再帰関数を回し、一番長いところと次に長いところまでの距離を計算して、グローバル変数として置いてある今までの最大値と比較して答えを更新する。そして返り値としては一番長いものを返す。再帰的に行なわれることによってこれで答えが求まる。

反省

　15分22秒でAC。これは簡単めな問題だったと思う。木の直径を求める方法なんて調べればすぐ出てくるとは思ったが、一応自力で考察して解くことができた。

　解説スライドを読むと木の直径を求める方法として

• 木DPをする
• ある頂点から最も遠い頂点を探し、さらにその頂点から最も遠い頂点を探す

　という2つが挙げられていた。自分の解法は上の木DPに相当すると思われるが、書いている最中は木DPという自覚はなかった。後者の方法は木の直径に絞られた解き方ではあるが、覚えておいて損はなさそうだ。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

vector<vector<ll>> connect;
ll global_max;
pair<ll, ll> ans;

pair<ll, ll> solve(ll curr, ll pre) {
    ll max1 = 0, max2 = 0;
    pair<ll, ll> p = { curr, curr };
    for (ll next : connect[curr]) {
        if (next == pre) {
            continue;
        }

        auto n = solve(next, curr);
        ll length = n.first + 1;

        if (length > max1) {
            max2 = max1;
            max1 = length;

            p.second = p.first;
            p.first = n.second;
        } else if (length > max2) {
            max2 = length;
            p.second = n.second;
        }
    }

    if (max1 + max2 > global_max) {
        ans = p;
        global_max = max1 + max2;
    }
    return { max1, p.first };
}

int main() {
    ll N;
    cin >> N;
    connect.resize(N);
    for (ll i = 0; i < N - 1; i++) {
        ll A, B;
        cin >> A >> B;
        A--; B--;
        connect[A].push_back(B);
        connect[B].push_back(A);
    }

    solve(0, -1);
    cout << ans.first + 1 << " " << ans.second + 1 << endl;
}