交互题
题意: 有一个节点 x, 每次可询问一个节点 v 到 x 距离, 或者 x 在一个节点 u 的哪个儿子的子树中, 最多询问 36 次, 找到 x 节点
题解: 链剖, 每次找深度最大的重儿子 v 到 x 的距离, 根据深度可找到 v 和 x 的 lca, 每两次询问可将目标范围缩小一半.
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- using namespace std;
- const int N=2e5+7;
- struct E {
- int v,next;
- }e[N<<1];
- int fa[N],dep[N],sz[N],son[N],head[N];
- int n,k,dx,u,v,s;
- void adde(int u,int v) {
- e[k].v=v;e[k].next=head[u];head[u]=k++;
- }
- void dfs(int u,int f) {
- fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;
- for (int i=head[u];~i;i=e[i].next) {
- int v=e[i].v;
- if (v==f) continue;
- dfs(v,u);sz[u]+=sz[v];
- if (!son[u]||sz[son[u]]<=sz[v]) son[u]=v;
- }
- }
- int main()
- {
- memset(head,-1,sizeof(head));
- scanf("%d",&n);
- for (int i=1;i<n;i++) {
- scanf("%d%d",&u,&v);
- adde(u,v);adde(v,u);
- }
- dep[0]=-1;
- dfs(1,0);
- u=1;
- cout << "d" << u << endl;
- fflush(stdout);
- scanf("%d",&dx);
- if (dx==0) {
- cout << "! 1" << endl;
- fflush(stdout);
- return 0;
- }
- while (1) {
- int v=u;
- while (son[v]) v=son[v];
- cout << "d" << v << endl;
- fflush(stdout);
- scanf("%d",&s);
- int dy=(dx+dep[v]-s)/2;
- while (dep[u]<dy) u=son[u];
- if (dep[u]==dx) {
- printf("! %d",u);
- fflush(stdout);
- break;
- }
- cout << "s" << u << endl;
- fflush(stdout);
- scanf("%d",&u);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3329833.html