Kuroni and the Celebration [Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!) D]

https://codeforces.com/contest/1305/problem/D

解説

https://codeforces.com/contest/1305/submission/72481693

木の葉から2つを選択して質問するという方針を繰り返す。
応答が指定した2つの頂点以外であれば、その葉が根である可能性はなくなる。
かつ、その葉を木から削除しても問題なくなる。
これは、今後その葉がLCA計算には影響しないためである。
これを繰り返していくと、1回で2つ消えるので、N/2回で答えが見つかる。
2つの頂点を選択して質問して、どちらかが応答で帰ってきたら、それが答え。
頂点が1つだけになったら、それを答える。

int N;
set<int> E[1010];
bool erased[1010];
//---------------------------------------------------------------------------------------------------
int query(int u, int v) {
    printf("? %d %d\n", u + 1, v + 1);
    fflush(stdout);
    int res; cin >> res;
    return res - 1;
}
//---------------------------------------------------------------------------------------------------
void answer(int r) {
    printf("! %d\n", r + 1);
    fflush(stdout);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].insert(b);
        E[b].insert(a);
    }

    rep(_, 0, 500) {
        int a = -1, b = -1;
        rep(i, 0, N) if (!erased[i] && E[i].size() <= 1) {
            if (a < 0) a = i;
            else b = i;
        }

        if (b < 0) {
            answer(a);
            return;
        }

        int res = query(a, b);
        if(res != a && res != b) {
            fore(to, E[a]) E[to].erase(a);
            fore(to, E[b]) E[to].erase(b);
            erased[a] = erased[b] = true;
        } else {
            answer(res);
            return;
        }
    }
}