解法
木の直径を求めるアルゴリズム．
- 任意に頂点を選び，\(v_{0}\) とする．
- \(v_{0}\) から最も遠い点の一つを \(v_{1}\) とする．
- \(v_{1}\) から最も遠い点の一つを \(v_{2}\) とする．
\(v_{1}, v_{2}\) が直径の一つ．
実装
始点を固定したとき，最も遠い点は DFSで求まる． つまり DFSを 2回実行すれば，木の直径が求まる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
ll question(ll a,ll b){
cout << "? " << a+1 << " " << b+1 << endl;
ll x; cin >> x;
return x;
}
int main() {
ll n;
cin >> n;
const ll inf = n * (ll)1e6;
auto f = [&](ll src) -> pll {
ll ma = -1, ind = -1;
rep(i,n) if(i!=src){
if(chmax(ma, question(src,i))){
ind = i;
}
}
return {ma, ind};
};
auto [_,i] = f(0);
auto [ma,__] = f(i);
cout << "! " << ma << endl;
return 0;
}
