题解 CF1044B 【Intersecting Subtrees】

有意思的交互题。

题意：

多测。

你和 Li Chen 各有一棵形态相同但标号不一定相同的树，你们分别选择了一个连通块，你知道你的树的节点编号、你选择的连通块每个点在你的树上的编号、Li Chen 选择的连通块每个点在他的树上的编号。

你可以用 A x 询问你的树上编号为 x 的点在他的树上的编号，或者用 B x 询问他的树上编号为 x 的点在你的树上的编号，最多进行 5 次询问。你需要用 C x 给出一个点 x（在你的树中的编号），使得它既在你的连通块里，也在 Li Chen 的连通块里，或者告诉我这样的点不存在。

我们可以先随便找一个 Li Chen 选了的点，然后询问在我的树上的编号。如果这个点我也选了，运气很好，直接输出答案即可。

但是如果我没选呢？

因为选的点都是连通的，而这个点没有被我选，说明我选的连通块一定在这个点为根的 一个 子树内，此时的树如图：（蓝色是那个 Li Chen 选的点，绿色是我选的连通块）

此时我的连通块中所有点的最近公共祖先一定也在连通块内，即图中最右边子树的根，可以通过一次 dfs 或者 bfs 来找到，我用的 bfs。

我们可以询问这个点在 Li Chen 的树中的编号，判断这个点是否在他的连通块内，如果在那这个点就是公共点，否则的话 Li Chen 的连通块在这个点的另一侧，而这个点没有取，所以我选的连通块子树的所有点都不能取到（因为取的所有点连通）。此时两个连通块没有交集。

对于每组数据：使用 2 次询问，时间复杂度 O(n)。

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
using namespace std;
typedef long long ll;
const int N = 1e3+5; 

int T, n, colA[N], colB[N], vis[N];
template<typename T> void chkmin(T &x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T &x, T y) {if(x < y) x = y;}
vector<int> a, b, e[N];
int ask(char op, int val) {
    printf("%c %d\n", op, val);
    fflush(stdout);
    int res = 0;
    if(op != 'C') {
        scanf("%d", &res);
        if(res == -1) exit(0);
    }
    return res;
}
int bfs(int s) {
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        if(colA[u]) return u;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int v : e[u]) {
            if(!vis[v]) q.push(v);
        }
    }
    return -1;
}

int main() {
    for(scanf("%d", &T);T;T--) {
        scanf("%d", &n);
        rep(i, 1, n-1) {
            int u, v;
            scanf("%d%d", &u, &v);
            e[u].push_back(v);
            e[v].push_back(u);
        }
        int k;
        scanf("%d", &k);
        a.resize(k);
        rep(i, 0, k-1) scanf("%d", &a[i]);
        for(int i : a) colA[i] = 1;
        scanf("%d", &k);
        b.resize(k);
        rep(i, 0, k-1) scanf("%d", &b[i]);
        for(int i : b) colB[i] = 1;
        int u = ask('B', b[0]);
        if(colA[u]) ask('C', u);
        else {
            int v = bfs(u);
            int qwq = ask('A', v);
            if(colB[qwq]) ask('C', v);
            else ask('C', -1);
        }
        rep(i, 1, n) colA[i] = colB[i] = vis[i] = 0;
        a.clear(); b.clear();
        rep(i, 1, n) e[i].clear();
    }
    return 0;
}