首页 > 其他 > 详细

CF563F. Ehab and the Big Finale

时间:2019-12-13 18:13:09      阅读:112      评论:0      收藏:0      [点我收藏+]

交互题

题意:有一个节点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

 

CF563F. Ehab and the Big Finale

原文:https://www.cnblogs.com/yglng/p/12036298.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!