algoNote

プログラミング関連

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1) B. Intersecting Subtrees

問題

http://codeforces.com/contest/1074/problem/B

解法

クエリの上限は5回ですが、2回で求まります。

まず、yの中から適当なラベルを選んで、自分の木での位置を質問します。この頂点をSとして、Sとxの頂点との距離が最小になる点をPとします。Pの位置の相手のラベルを質問して、これがyに含まれていればPが答えです。そうでなければ共有点はありません。

Pの求め方ですが、Sがxの部分木中に含まれれば、P=Sです。そうでない場合、適当に根を決めると、xの部分木はSの下側か上側にあることになります。

ここで、根付き木上でxの中で一番上にある点をT、xの中で部分木にSを含む頂点のうち一番下にあるものをB(存在するなら)とおくと、Bが存在するならP=Bで、そうでないならP=Tです。

xの部分木がSの上側にあるケースのイメージ
f:id:algon_320:20181108225630p:plain

xの部分木がSの下側にあるケースのイメージ
f:id:algon_320:20181108225637p:plain

提出コード

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

// in, out: 0-indexed
int ask(char type, int x) {
    cout << type << " " << x + 1<< endl;
    int y;
    cin >> y;
    if (y == -1) exit(0);
    return y - 1;
}
// in: 0-indexed
void answer(int v) {
    cout << "C " << v + 1 << endl;
}
signed main() {
    int Q;
    cin >> Q;
    while (Q--) {
        int n;
        cin >> n;
        vector<vector<int>> g(n);
        REP(i, n - 1) {
            int a, b;
            cin >> a >> b;
            a--, b--;
            g[a].pb(b);
            g[b].pb(a);
        }

        int k1;
        cin >> k1;
        vector<int> x(k1);
        cin >> x; FORE(i, x) i--;
        sort(ALL(x));

        int k2;
        cin >> k2;
        vector<int> y(k2);
        cin >> y; FORE(i, y) i--;
        sort(ALL(y));

        vector<bool> color(n);
        FORE(i, x) color[i] = true;

        int S = ask('B', y[0]);
        if (color[S]) {
            answer(S);
            continue;
        }

        int T = -1;
        auto findT = [&](auto f, int v, int p) -> void {
            if (color[v] && T == -1) T = v;
            FORE(w, g[v]) {
                if (w == p) continue;
                f(f, w, v);
            }
        };
        findT(findT, 0, -1);

        int B = -1;
        auto dfs = [&](auto f, int v, int p) -> bool {
            if (v == S) return true;
            bool found = false;
            FORE(w, g[v]) {
                if (w == p) continue;
                bool res = f(f, w, v);
                if (res && color[v] && B == -1) B = v;
                found |= res;
            }
            return found;
        };
        dfs(dfs, 0, -1);

        if (B != -1) {
            if (binary_search(ALL(y), ask('A', B))) {
                answer(B);
            } else {
                cout << "C -1" << endl;
            }
        } else {
            if (binary_search(ALL(y), ask('A', T))) {
                answer(T);
            } else {
                cout << "C -1" << endl;
            }
        }
    }
    return (0^_^0);
}

インタラクティブな問題では#define endl "\n"してはいけません...