abc 019 D - 高橋くんと木の直径

問題

問題概要

木の直径を求める問題。

解法

木の直径を求めるアルゴリズムは、
1.任意の頂点sから最も遠い頂点をxを求める
2.頂点xから、最も遠い頂点yを求める
3.頂点xからyの距離が木の直径となる
これを実装すればいい。

ミス

なし。

コード

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)


int main(void){
    int n; cin >> n;
    int s = 1, u, v;
    //sから最も遠い　u を求める
    int ma = 0;
    for (int i = 1; i <= n; ++i){
        if(s != i){
            int dist;
            cout << "? " << s << " " << i << endl;
            cin >> dist;
            if(dist > ma){
                ma = max(ma, dist);
                u = i;
            }
        }
    }

    //uから最も遠いvまでの距離が木の直径となる
    int ans = 0;
    for (int i = 1; i <= n; ++i){
        if(u != i){
            int dist;
            cout << "? " << u << " " << i << endl;
            cin >> dist;
            if(dist > ans){
                ans = max(ans, dist);
            }
        }
    }
    cout << "!" << " " << ans << endl;
    return 0;
}