木の直径の求め方を知っていれば解ける!!
問題概要
頂点数 の木があるが、その形状についての情報はあらかじめわからない。あなたの目的は、この木の直径の長さを求めることである。
そのために、以下のクエリを 100 回まで投げることができる。
「2 頂点 を指定して、パス - の長さを聞く」
100 回以内のクエリによって、直径の長さを当ててほしい。
制約
考えたこと
木が与えられたときに、木の直径は次の手順で求められることが知られている。
- 適当な頂点 を 1 つ選ぶ
- 頂点 から最も遠い頂点 を求める
- 頂点 から最も遠い頂点 を求める
このとき、パス - が直径になるのだ。このことを知っていると、今回の問題はもう解けたも同然だ。
- なにか適当な頂点 を選び、 以外の各頂点との距離を問いて、それが最大となる頂点 を見つける ( 回)
- 頂点 から、それ以外の各頂点との距離を問いて、その最大値を求める ( 回)
合計で 回なので、制限回数以内に求められる。
コード
直径ライブラリは特に必要なかった。
#include <bits/stdc++.h> using namespace std; int main() { int N, dist; cin >> N; int u = 0, vmx = -1, mx = 0; for (int v = 1; v < N; ++v) { cout << "? " << u+1 << " " << v+1 << endl; cin >> dist; if (mx < dist) { mx = dist; vmx = v; } } for (int w = 0; w < N; ++w) { if (w == vmx) continue; cout << "? " << vmx+1 << " " << w+1 << endl; cin >> dist; mx = max(mx, dist); } cout << "! " << mx << endl; }