题目大意:
已知有一个n个节点的树。我们可以询问n/2(向下取整)次任意两个节点的LCA(关于什么是LCA https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/),问我们怎么确定根节点。
n<=1e3
解题思路:
因为这里的n的范围,我们考虑n^2的算法。
首先有一个结论:我们每次询问两个度数为1节点(u,v)的LCA,假如LCA=u或者LCA=v,那么root肯定是LCA。这个可以用反证法证明。对于u,v其中一个度数不为1的话,这个结论不成立,因为u,v其中一个是LCA只代表u或者v中谁更在低层而已。
所以我们每次枚举任意两个叶子节点(叶子节点即度数为1的点),若得出LCA是正在询问的两个点中的一个,我们则退出。若不是,我们可以删掉这两个叶子继续重复询问。这样就能n/2次完成询问并且得到根节点。
这里利用了度数这个概念,做图论题的时候度数有时候是个不错的入手点,类似的还有拓扑排序的题目。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;cin>>n;
int deg[n];
memset(deg,0,sizeof(deg));
vector<vector<int>> gra(n);
set<int> ms;
for(int i=0;i<n-1;i++){
int u,v;cin>>u>>v;
u--;v--;
deg[u]++;
deg[v]++;
gra[u].push_back(v);
gra[v].push_back(u);
ms.insert(i);
}
ms.insert(n-1);
int l,r;
l=r=-1;
while(1){
l=-1;r=-1;
for(int i=0;i<n;i++){
if(deg[i]==1){
if(l==-1)l=i;
else r=i;
}
}
if(l==-1 || r==-1)break;
printf("? %d %d\n",l+1,r+1);
fflush(stdout);
// cerr<<l<<" "<<r<<endl;
int w;cin>>w;
w--;
if(w==l || w==r){
printf("! %d\n",w+1);
fflush(stdout);
return 0;
}
deg[l]--;
for(int i=0;i<(int)gra[l].size();i++){
int nx=gra[l][i];
deg[nx]--;
}
deg[r]--;
for(int i=0;i<(int)gra[r].size();i++){
int nx=gra[r][i];
deg[nx]--;
}
ms.erase(l);
ms.erase(r);
}
assert(ms.size());
printf("! %d\n",*ms.begin()+1);
fflush(stdout);
return 0;
}