CF1370F2

Purslane · 2024-04-09 23:43:42 · 题解

Solution

唐人做唐题。考虑 \text{query}(\{1,2,3,\dots,n\})，得到了两个关键点之间的距离和他们路径上的某一个节点 u。

以 u 为根，两个关键点 c 和 d 在两个不同的子树内。

考虑到 c 和 d 之间的路径和一个水平面（深度相同的点）只有一个交点，那么就可以通过二分得到较深的那一个点，设为 c。

再以 c 为根，按照 c 和 d 之间的距离画一个水平面，与路径也只有一个交点，为 d。

这样需要 2+ \log(n) 次询问。

注意到我们是找到较深点，所以它所在的可能深度范围小于等于 \dfrac{n}{2}，审掉了一次询问。

可以通过 \rm Easy \ version 和 \rm Hard \ version。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1000+10;
int n,T,dis[MAXN],dep[MAXN];
vector<int> G[MAXN];
pair<int,int> query(vector<int> vc) {
    if(vc.empty()) return {0,0};    
    cout<<"? "<<vc.size()<<' ';for(auto id:vc) cout<<id<<' ';cout<<endl;
    int x,d; cin>>x>>d;
    return {x,d};
}
void dfs(int u,int f,int *dis) {
    dis[u]=dis[f]+1;
    for(auto v:G[u]) if(v!=f) dfs(v,u,dis);
    return ;    
}
vector<int> gen(int deep) {
    vector<int> ans;
    ffor(i,1,n) if(dep[i]==deep) ans.push_back(i);
    return ans; 
}
int main() {
    cin>>T;
    while(T--) {
        cin>>n; ffor(i,1,n) G[i].clear();
        ffor(i,1,n-1) {int u,v; cin>>u>>v,G[u].push_back(v),G[v].push_back(u);}
        vector<int> vc; ffor(i,1,n) vc.push_back(i);
        auto pr=query(vc); int len=pr.second,rt=pr.first;
        dfs(rt,0,dep);
        int L=(len+1)/2,R=len,ans=0;
        while(L<=R) {
            int mid=L+R>>1;
            auto pr=query(gen(mid+1));
            if(pr.second==len) ans=pr.first,L=mid+1;
            else R=mid-1;   
        }
        dfs(ans,0,dep);
        int ot=query(gen(len+1)).first;
        cout<<"! "<<ans<<' '<<ot<<endl;
        string result; cin>>result;
    }
    return 0;
}