# ARC142-C Tree Queries

diff1347
https://atcoder.jp/contests/arc142/tasks/arc142_c

## 解法

$v = 3, 4, \dots, N$について頂点$1$からの距離と頂点$2$からの距離をそれぞれ質問して求めておく($2N - 4$回の質問)。

$S = \{ v\ |\ d_{2v} = 1, 3\le v\le N \}$とする。

**$S = \emptyset$のとき**

木は連結という条件から、頂点$2$は頂点$1$と隣接していなければならない。$d_{12} = 1$である。

**$|S| \gt 1$のとき**


頂点$2$の次数が2以上であることがわかる。この場合は $d_{12} = -1 + \max_{v\in S} d_{1v}$が成り立つ

**$|S| = 1$のとき**


この２つのパターンがある。

$T = \{ v\ |\ d_{1v} = d_{2v}, 3\le v\le N\}$とする。

$T$が非空ならば必ず上のパターンである。$\min_{v\in T} 2\times d_{1v}$が解となる。

次に、$d_{1p} = 1, d_{2p} = 2$を満たす頂点$p$と$d_{1q} = 2, d_{2q} = 1$を満たす頂点$q$が存在するか調べる。存在するなら$p, q$を適当にとって、$d_{pq}$を質問する。$d_{pq} = 1$ならば上のパターン($d_{12} = 3$)、$d_{pq} = 3$ならば下のパターン($d_{12} = 1$)である。$d_{pq}$は必ず$1$か$3$である。

$T$が空である場合、上のパターンまたは、下のパターンかつ頂点$1$が頂点$2$としか隣接していないことがわかる。$v = 3, 4, \dots, N$について$d_{1v}\gt d_{2v}$が成り立つならば後者とわかり、$d_{12} = 1$である。そうでなければ前者であるので、$S$の唯一の要素を$v$として$d_{1v} + 1$である。

## 実装

#include <bits/stdc++.h>

int ask(int i, int j) {
    i++;
    j++;
    std::cout << '?' << ' ' << i << ' ' << j << std::endl;
    int d;
    std::cin >> d;
    if (d == -1) std::exit(0);
    return d;
}

int answer(int d) {
    std::cout << '!' << ' ' << d << std::endl;
    std::exit(0);
}


int main() {
    int N;
    std::cin >> N;
    std::vector<int> d1(N), d2(N); 
    for (int i{2} ; i < N ; i++) {
        d1[i] = ask(0, i);
        d2[i] = ask(1, i);
    }
    std::vector<int> adj1;
    for (int i{2} ; i < N ; i++) if (d2[i] == 1) adj1.push_back(d1[i]);
    std::sort(adj1.begin(), adj1.end());
    if (adj1.empty()) {
        answer(1);
    }
    if (adj1.size() > 1u) {
        answer(adj1.back() - 1);
    }
    const int INF{(int)1e9};
    int same{INF};
    for (int i{2} ; i < N ; i++) if (d1[i] == d2[i]) {
        same = std::min(same, d1[i]);
    }
    if (same < INF) answer(2 * same);
    for (int i{2} ; i < N ; i++) if (d1[i] == 1 and d2[i] == 2) {
        for (int j{2} ; j < N ; j++) if (d1[j] == 2 and d2[j] == 1) {
            int d{ask(i, j)};
            if (d == 1) {
                answer(3);
            }
            else if (d == 3) {
                answer(1);
            }
            else while (true) ;
        }
    }
    bool allbig{true};
    for (int i{2} ; i < N ; i++) allbig &= d1[i] > d2[i];
    if (allbig) answer(1);
    answer(adj1[0] + 1);
}

[提出](https://atcoder.jp/contests/arc142/submissions/58113679)

## 感想

やっぱ構築・インタラクティブは嫌いだね〜〜〜〜〜

想定解もこんな感じだったら暴れます。想定解綺麗だったらorzってことで...
- いつも解説を見る前に記事を書いている