CF1044B Intersecting Subtrees 题解

· · 题解

这题需要一些对树形结构的了解。

先从已知的 Li Chen 的树上有染色的点随便选一个来询问它在“我”的树上的编号，如果该点被染色，答案即为该点。如果该点没有被染色，找出在“我”的树上离这个最近的有染色的点再进行一次询问，如果 Li Chen 的树上的该点有染色那么该点就是答案，否则无解。

尝试证明为什么如果 Li Chen 的树上第二次询问的点没有染色一定无解。显然“我”的树上有染色的点构成的子树把整个树的没染色的点分成了若干棵互不相交的子树，第二次询问的点即为 Li Chen 的子树和“我”的子树有可能相交的地方。如果 Li Chen 的这个点没有被染色，那么 Li Chen 的子树必然被“我”的有染色子树隔绝在了那互不相交的子树中的一个之中，不可能再通过其他的点和“我”的有染色子树相交。

时间复杂度 O(Tn)，询问次数最多为 2，足以通过题目。

代码实现较为容易。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,s; cin>>n;
    vector<vector<int> > g(n);
    vector<bool> b(n),b2(n),v(n);
    for(int i=1;i<n;i++){
      int u,v; cin>>u>>v;
      g[u].emplace_back(v);
      g[v].emplace_back(u);
    }
    int k; cin>>k;
    while(k--){
      int x; cin>>x;
      b[x-1]=true;
    }
    cin>>k;
    while(k--){
      int x; cin>>x;
      b2[s=x-1]=true;
    }
    cout<<"B "<<s+1<<endl;
    cin>>s;
    if(b[--s]){
      cout<<"C "<<s<<endl;
      continue;
    } // 第一轮的点就满足条件
    queue<int> q;
    q.emplace(s),v[s]=true;
    while(!q.empty()){
      int u=q.front(); q.pop();
      if(b[u]){s=u+1; break;}
      for(int i:g[u])
        if(!v[i])v[i]=true,q.emplace(i);
    } //  BFS 找最近的点
    cout<<"A "<<s<<endl;
    int x; cin>>x;
    if(b2[x-1])cout<<"C "<<s<<endl;
    else cout<<"C -1"<<endl;
  }
  return 0;
}