题目大意

题目链接

给你一棵n个节点的树， 找出他的根结点。

交互(不懂交互题的百度搜例题就明白了)

最多可以交互 n / 2次
输出 ? u v 返回 lca(u, v) .
输出答案 ! root

分析

最多询问n / 2 次， 如果保证每次都能淘汰两个点的话， 肯定能找到根结点，如果n为奇数并且 在n / 2次内没找到根结点， 那么剩下的那个节点就是根结点。
就是自己搞一搞。
我选择的是每次选择叶子节点， 如果 lca(u, v) == u || lca(u, c) == v 那么 lca(u, v) 就是根结点。如果不是， 那么就把这两个叶子节点删除， 这样有可能会有新的叶子节点， 再把它放到队列中。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
power by Solo_Dance
*/
#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;

inline ll read() {
    ll res = 0;bool f = 0;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = 1;ch = getchar();}
    while (ch <= '9' && ch >= '0') {res = (res << 3) + (res << 1) + ch - '0';ch = getchar();}
    return f ? (~res + 1) : res;
}
int n;
int du[1003];
vector<int>ma[1003];
int main(){
    cin >> n;
    for (int i = 0; i < n - 1; ++i){
        int a, b;
        cin >> a >> b;
        ma[a].push_back(b);
        ma[b].push_back(a);
        du[a]++, du[b]++;
    }
    queue<int>q;
    int sum = n / 2;
    for (int i = 1; i <= n; ++i)
        if (du[i] == 1) q.push(i);

    while(!q.empty() && sum--){
        int c1 = q.front();q.pop();
        if (q.empty()) break;
        int c2 = q.front();q.pop();
        cout << "? " << c1 << " " << c2 << endl;
        int lca;
        cin >> lca;
        if (lca == c1 || lca == c2){
            cout << "! " << lca << endl;
            return 0;
        }
        du[c1] = du[c2] = -1;
        for (auto c : ma[c1]) {
            du[c]--;
            if (du[c] == 1) q.push(c);
        }

        for (auto c : ma[c2]) {
            du[c]--;
            if (du[c] == 1) q.push(c);
        }

    }
    for (int i = 1; i <= n; ++i){
        if (du[i] >= 0)
            cout << "! " << i << endl;
    }

    return 0;
}
恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan

千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。