題目鏈接：點擊查看

題目大意：給出一個由 n 個點組成的樹，現在可以詢問 n/2 次(向下取整)LCA，確定根節點是哪個節點

題目分析：因為最多只能求 n/2 次lca，每次需要兩個節點作為參數，也就是說每個點我們至多遍歷一遍，讀完題后沒什么思路，隊友給我提示說可以參考樹上啟發式合并的思想，從葉子結點向上不斷合并找到根節點，由此我感覺可以根據度來找到葉子結點，每次詢問兩個葉子結點的LCA，直到存在著某次的LCA等于葉子結點就找到根節點了，因為如果兩個葉子結點的LCA不是兩者之一的話，那么說明這兩個葉子結點必定不可能是根節點，所以直接扔掉就好了，如此往復，從外向內，首先滿足特判的點肯定就是根節點了，具體證明我不太會證，不過仔細想一下應該也就是這樣一回事了

有個小坑需要注意一下，因為詢問的次數是 n/2 向下取整，對于奇數而言，最后肯定會有一個節點無法被訪問到，這里記得特判一下就好了，如果在前 n - 1 個點中都沒有找到根節點的話，那么最后這個點肯定就是根節點了呀

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e3+100;vector<int>node[N];int du[N];int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);du[u]++,du[v]++;}int limit=n/2;queue<int>q;for(int i=1;i<=n;i++)if(du[i]==1)q.push(i);while(q.size()>1&&limit--){int cur1=q.front();q.pop();int cur2=q.front();q.pop();du[cur1]=du[cur2]=-1;printf("? %d %d\n",cur1,cur2);fflush(stdout);int lca;scanf("%d",&lca);if(lca==cur1||lca==cur2){printf("! %d\n",lca);return 0;}for(auto u:node[cur1])du[u]--;for(auto u:node[cur2])du[u]--;while(q.size())q.pop();for(int i=1;i<=n;i++)if(du[i]==1)q.push(i);}for(int i=1;i<=n;i++)if(du[i]>=0)printf("! %d\n",i);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1305D Kuroni and the Celebration(思维，互动题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。