249642026-02-17 10:16:33Leventusz09Where Is the Root?cpp17Belső hiba
#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int degree;
    vector<int> et;
} G[500];

int count(int index, int q){
    if(index == -1) return 0;
    int c = 1;
    for(const int&e:G[index].et){
        if(e == q) continue;
        c += count(e, index);
    }
    return c;
}

signed main(){
    int N;
    cin >> N;

    for(int i=1; i<N; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        G[x].et.push_back(y);
        G[y].et.push_back(x);
        G[x].degree++;
        G[y].degree++;
    }

    char input[4];
    while(true){
        // legnagypbb fokszám keresése
        int mi = 0;
        for(int i=1; i<N; i++) if(G[i].degree > G[mi].degree) mi = i;
        
        // kettéosztás
        int es[G[mi].et.size()];
        for(int i=0; i<G[mi].et.size(); i++) es[i] = count(G[mi].et[i], mi);
        
        // 1. kettéosztási algoritmus
        // legnagyobb - összes többi
        //#if true
        if(G[mi].degree == 2){
            cout << "? 2 " << G[mi].et[0] + 1 << " " << G[mi].et[1] + 1 << endl;
            cout.flush();
            cin >> input;
            if(input[0] == 'Y'){
                cout << "? 2 " << mi + 1 << " " << G[mi].et[0] + 1 << endl;
                cout.flush();
                cin >> input;
                if(input[0] == 'Y'){
                    cout << "! " << G[mi].et[0] + 1 << endl;
                    return 0;
                }else{
                    cout << "! " << G[mi].et[1] + 1 << endl;
                    return 0;
                }
            }else{
                cout << "! " << mi +1 << endl;
                return 0;
            }
        }

        int emi = 0;
        for(int i=1; i<G[mi].et.size(); i++) if(es[i] > es[emi]) emi = i;

        cout << "? " << G[mi].et.size() - 1;
        for(int i=0; i<G[mi].et.size(); i++) if(i != emi) cout << " " << G[mi].et[i] + 1;
        cout << endl;
        cout.flush();
        
        cin >> input;
        if(input[0] == 'Y'){
            // jujj, itt mit is csinálunk?
        }else{
            for(int i=0; i<G[mi].et.size(); i++) if(i != emi) G[mi].et[i] = -1;
            G[mi].degree -= G[mi].et.size() - 1;
        }
        //#endif
    }
}