题目链接:点击查看
题目大意:给出一个由 n 个点组成的树,现在可以询问 n/2 次(向下取整)LCA,确定根节点是哪个节点
题目分析:因为最多只能求 n/2 次lca,每次需要两个节点作为参数,也就是说每个点我们至多遍历一遍,读完题后没什么思路,队友给我提示说可以参考树上启发式合并的思想,从叶子结点向上不断合并找到根节点,由此我感觉可以根据度来找到叶子结点,每次询问两个叶子结点的LCA,直到存在着某次的LCA等于叶子结点就找到根节点了,因为如果两个叶子结点的LCA不是两者之一的话,那么说明这两个叶子结点必定不可能是根节点,所以直接扔掉就好了,如此往复,从外向内,首先满足特判的点肯定就是根节点了,具体证明我不太会证,不过仔细想一下应该也就是这样一回事了
有个小坑需要注意一下,因为询问的次数是 n/2 向下取整,对于奇数而言,最后肯定会有一个节点无法被访问到,这里记得特判一下就好了,如果在前 n - 1 个点中都没有找到根节点的话,那么最后这个点肯定就是根节点了呀
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<ctime> 5 #include<cmath> 6 #include<cstring> 7 #include<algorithm> 8 #include<stack> 9 #include<climits> 10 #include<queue> 11 #include<map> 12 #include<set> 13 #include<sstream> 14 using namespace std; 15 16 typedef long long LL; 17 18 typedef unsigned long long ull; 19 20 const int inf=0x3f3f3f3f; 21 22 const int N=1e3+100; 23 24 vector<int>node[N]; 25 26 int du[N]; 27 28 int main() 29 { 30 #ifndef ONLINE_JUDGE 31 // freopen("input.txt","r",stdin); 32 // freopen("output.txt","w",stdout); 33 #endif 34 // ios::sync_with_stdio(false); 35 int n; 36 scanf("%d",&n); 37 for(int i=1;i<n;i++) 38 { 39 int u,v; 40 scanf("%d%d",&u,&v); 41 node[u].push_back(v); 42 node[v].push_back(u); 43 du[u]++,du[v]++; 44 } 45 int limit=n/2; 46 queue<int>q; 47 for(int i=1;i<=n;i++) 48 if(du[i]==1) 49 q.push(i); 50 while(q.size()>1&&limit--) 51 { 52 int cur1=q.front();q.pop(); 53 int cur2=q.front();q.pop(); 54 du[cur1]=du[cur2]=-1; 55 printf("? %d %d\n",cur1,cur2); 56 fflush(stdout); 57 int lca; 58 scanf("%d",&lca); 59 if(lca==cur1||lca==cur2) 60 { 61 printf("! %d\n",lca); 62 return 0; 63 } 64 for(auto u:node[cur1]) 65 du[u]--; 66 for(auto u:node[cur2]) 67 du[u]--; 68 while(q.size()) 69 q.pop(); 70 for(int i=1;i<=n;i++) 71 if(du[i]==1) 72 q.push(i); 73 } 74 for(int i=1;i<=n;i++) 75 if(du[i]>=0) 76 printf("! %d\n",i); 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 return 0; 92 }