网站建设设计公司 知乎,滕州盛扬网站建设推广,国内优秀网站网页设计,安卓手机软件开发外包正题
题目链接:https://www.luogu.com.cn/problem/CF1370F2 题目大意 TTT组数据#xff0c;给出nnn个点的一棵树#xff0c;有两个隐藏的关键点。你每次可以询问一个点集#xff0c;交互库会回答这个点集中的一个点满足它到两个关键点的距离和最小#xff0c;和这个距离。…正题
题目链接:https://www.luogu.com.cn/problem/CF1370F2 题目大意
TTT组数据给出nnn个点的一棵树有两个隐藏的关键点。你每次可以询问一个点集交互库会回答这个点集中的一个点满足它到两个关键点的距离和最小和这个距离。
要求在111111次询问内求出这两个关键点。
1≤T≤10,1≤n≤10001\leq T\leq 10,1\leq n\leq 10001≤T≤10,1≤n≤1000 解题思路
首先第一下不知道干啥就问整张图吧。
这样我们就得到了一个点rtrtrt和距离LLL。这个点rtrtrt一定在关键点u,vu,vu,v的路径上且LLL表示u,vu,vu,v之间的距离。
然后就好搞了我们以rtrtrt为根考虑利用这个LLL来搞点操作我们每次选择一个深度depdepdep然后询问所有这个深度的点的话如果得到的距离等于LLL就表示这个深度有u∼vu\sim vu∼v路径上的点。
也就是我们可以通过二分得到最深的位置而最深的位置一定是离rtrtrt较远的一个关键点uuu。
而我们又知道两个关键点的距离以uuu为根询问一遍深度LLL的节点就可以得到vvv了。
二分上界是min{L,depmax}min\{L,dep_{max}\}min{L,depmax}所以次数是log(n)2≤12log(n)2\leq 12log(n)2≤12。好像多了一次
再挖掘一下性质发现我们找的是离rtrtrt较远的一个关键点所以这段距离一定是不小于⌊L−12⌋\lfloor\frac{L-1}{2}\rfloor⌊2L−1⌋的这样就可以少去一次了 code
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N1100;
struct node{int to,next;
}a[N1];
int T,n,tot,ls[N],mx;
vectorint v[N];char s[10];
void print(int x)
{if(x9)print(x/10);putchar(48x%10);return;}
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x,int fa,int dep){v[dep].push_back(x);mxmax(mx,dep);for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dfs(y,x,dep1);}return;
}
int main()
{scanf(%d,T);while(T--){memset(ls,0,sizeof(ls));totmx0;for(int i0;in;i)v[i].clear();scanf(%d,n);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}printf(? %d ,n);for(int i1;in;i)print(i),putchar( );putchar(\n);fflush(stdout);int rt,L,u,uu;scanf(%d%d,rt,L);dfs(rt,0,0);uuurt;int l(L-1)/21,rmin(L,mx);while(lr){int mid(lr)1;printf(? %d ,v[mid].size());for(int i0;iv[mid].size();i)print(v[mid][i]),putchar( );putchar(\n);fflush(stdout);int x,d;scanf(%d%d,x,d);if(dL)lmid1,ux;else rmid-1;}v[L].clear();dfs(u,0,0);printf(? %d ,v[L].size());for(int i0;iv[L].size();i)print(v[L][i]),putchar( );putchar(\n);fflush(stdout);scanf(%d%d,uu,L);printf(! %d %d\n,u,uu);fflush(stdout);scanf(%s,s1);}
}
