CF1305D Kuroni and the Celebration

題意：

給你一棵有 n 個節點的樹。對于每次詢問，提交兩個點，評測機會返回這兩個點的 LCA。求樹根。

詢問格式為 ? u v，此時評測機會返回 u 和 v 的 LCA。

提交格式為 ! x，表示你得出樹根為點 x。

你可以最多詢問 $?\frac{n}{2}?$次

題解：

如果一個葉子和另一個點的LCA是這個葉子，那么這個葉子一定為根
否則，這個葉子一定不是根
所以我們可以每次詢問兩個葉子的LCA即可，如果是其中一個點，則那個點就是根；否則刪除這個兩個點,有可能得到新的葉子節點，用得到的LCA去和剩下的葉子節點繼續求LCA
最壞情況每次刪除兩個葉子節點，那么$?\frac{n}{2}?$次后最多只剩下一個點，這就是根

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn=1020; vector<int>vec[maxn]; int d[maxn]; int main() {//rd_test();int n;read(n);for(int i=1;i<n;i++){int u,v;read(u,v);vec[u].push_back(v);vec[v].push_back(u);d[u]++;d[v]++;}queue<int>q;for(int i=1;i<=n;i++){if(d[i]==1)q.push(i);}int lca;while(!q.empty()){ // if(q.size()==0)printf("! %d\n",lca);int x=q.front();q.pop();if(q.size()==0)return printf("! %d\n",x),0;int y=q.front();q.pop();printf("? %d %d\n",x,y);cin>>lca;if(lca==x)return printf("! %d\n",x),0;else if(lca==y)return printf("! %d\n",y),0;for(auto v:vec[x])if((--d[v])==1)q.push(v);for(auto v:vec[y])if((--d[v])==1)q.push(v);// if(tot>n/2)break;} // cout<<lca<<endl;//Time_test(); }

總結

以上是生活随笔為你收集整理的CF1305D Kuroni and the Celebration的全部內容，希望文章能夠幫你解決所遇到的問題。

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