高橋くんと木の直径

• 高橋くんと木の直径

考察

• 最大で100回まで聞ける。
• 頂点数は最大で50。
• なので、1を始点とする最大の距離とその終点vを求める。
• そんで、vを始点とする最大の距離を求める。
• 結果、その距離が答えとなる

コード

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> G[55];

int main() {
    cin >> N;

    // 始点を1とする最大の距離とその終点を求める
    int maxDist = 0;
    int start = 1, end = 0;
    for (int i = 1; i <= N; i++) {
        if (start == i) continue;
        cout << "? " << start << " " << i << endl;
        int dist;
        cin >> dist;
        if (dist > maxDist) {
            maxDist = dist;
            end = i;
        }
    }

    // 始点をendとする最大の距離とその終点を求める
    start = end, end = 0;
    maxDist = 0;
    for (int i = 1; i <= N; i++) {
        if (start == i) continue;
        cout << "? " << start << " " << i << endl;
        int dist;
        cin >> dist;
        if (dist > maxDist) {
            maxDist = dist;
            end = i;
        }
    }

    cout << "! " << maxDist << endl;

    return 0;
}