Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!)D（交互，DFS）

每次查询两个叶子结点并把他们从树上删除，最终返回的答案就是根节点。

 1 #define HAVE_STRUCT_TIMESPEC
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 vector<int>v[1007];
 5 int dep[1007],pre[1007];
 6 int vis[1007];
 7 void dfs(int x,int fa){
 8     for(int i=0;i<v[x].size();++i){
 9         if(v[x][i]==fa)
10             continue;
11         dep[v[x][i]]=dep[x]+1;
12         pre[v[x][i]]=x;
13         dfs(v[x][i],x);
14     }
15 }
16 int main(){
17     ios::sync_with_stdio(false);
18     cin.tie(NULL);
19     cout.tie(NULL);
20     int n;
21     cin>>n;
22     for(int i=1;i<n;++i){
23         int x,y;
24         cin>>x>>y;
25         v[x].emplace_back(y);
26         v[y].emplace_back(x);
27     }
28     int st=1;
29     for(int t=1;t<=n/2;++t){
30         dep[st]=0;
31         dfs(st,st);
32         int x=st,y=st;
33         for(int i=1;i<=n;++i)
34             if(!vis[i]&&dep[i]>dep[x])
35                 x=i;
36         dep[x]=0;
37         dfs(x,x);
38         for(int i=1;i<=n;++i)
39             if(!vis[i]&&dep[i]>dep[y])
40                 y=i;
41         cout<<"? "<<x<<" "<<y<<"
";
42         cout.flush();
43         int now;
44         cin>>now;
45         int temp=y;
46         vis[x]=1;
47         while(temp!=x){
48             vis[temp]=1;
49             temp=pre[temp];
50         }
51         vis[now]=0;
52         st=now;
53     }
54     cout<<"! "<<st;
55     cout.flush();
56     return 0;
57 }