正解:构造

解题报告:

传送门

又是一道交互题!爱了爱了!

这题真的,极妙!非常神仙!就非常非常思维题!

直接说解法了吼

说起来实在是简单鸭

就是先问一个对方的联通块中的一个点在我这儿的编号,记为x

如果x就是我联通块中的肯定公共点就是x,continue,不讨论运气这么好的事儿x

然后问我的联通块中离x最近的点在对方那儿的编号,记为y

如果y属于对方的联通块,欧克,说明有公共点,就是y

如果不属于,那就麻油公共点,GG

解释一下吼

如果属于这个不用说趴显然

然后如果不属于,我们令x为树根,那么我这个联通块一定都在x的一棵子树上(因为麻油经过x嘛

然后离x最近的这个节点就是这个子树的根

如果根都不在对方的联通块中其它节点就更麻油机会了鸭

所以就麻油公共点!over!

(不知道为什么,,,我明明是用的psj教的方法做的但是他的代码跑得飞快我跑得飞慢,,,就很难过TT

#include <bits/stdc++.h>

using namespace std;

#define ll int

#define il inline

#define rg register

#define rp(i,x,y) for(register ll i=x;i<=y;++i)

const ll N=+;

struct ed{ll from,to,nxt;void clr(){from=;to=;nxt=;}}edge[N<<];

ll head[N],cnt;

bool my[N],your[N];

il void ad(int x,int y){edge[++cnt].to=y;edge[cnt].nxt=head[x];head[x]=cnt;}

il ll dfs(int num,int fa)

{

    if(my[num])return num;

    for(rg ll i=head[num];i;i=edge[i].nxt)

    {

        if(edge[i].to==fa)continue;

        ll temp=dfs(edge[i].to,num);

        if(temp!=-)return temp;

    }

    return -;

}

int main()

{

    ll T;cin>>T;

    while(T--)

    {

        ll n,tmp,gdgs,root;cin>>n;

        memset(head,,sizeof(head));rp(i,,(n<<))edge[i].clr();memset(my,,sizeof(my));memset(your,,sizeof(your));cnt=;

        rp(i,,n-){ll x,y;cin>>x>>y;ad(x,y);ad(y,x);}

        cin>>tmp;rp(i,,tmp)cin>>gdgs,my[gdgs]=;cin>>tmp;rp(i,,tmp)cin>>gdgs,your[gdgs]=;

        cout<<"B "<<gdgs<<endl;cout.flush();cin>>root;

        if(my[root]){cout<<"C "<<root<<endl;cout.flush();continue;}

        ll ques=dfs(root,);

        if(ques==-){cout<<"C -1\n";cout.flush();continue;}

        cout<<"A "<<ques<<endl;cout.flush();

        ll as;cin>>as;

        if(your[as]){cout<<"C "<<ques<<endl;cout.flush();continue;}

        cout<<"C -1\n";cout.flush();

    }

    return ;

}

我做出了我人生中第一道交互题呜呜呜!

构造

CF1044B Intersecting Subtrees 构造+树论

正解:构造

解题报告: