/* -*- coding: utf-8 -*- * * 3237.cc: No.3237 Find the Treasure! - yukicoder */ #include #include #include #include using namespace std; /* constant */ const int MAX_N = 10000; /* typedef */ using vi = vector; using pii = pair; /* global variables */ vi nbrs[MAX_N]; pii es[MAX_N]; int ps[MAX_N], cis[MAX_N], ds[MAX_N]; int xs[MAX_N]; bool used[MAX_N]; /* subroutines */ bool query(int m, int xs[]) { putchar('?'); for (int i = 0; i < m; i++) printf(" %d", xs[i] + 1); putchar('\n'); fflush(stdout); char s[16]; scanf("%s", s); if (s[0] == 'I') exit(0); return (s[0] == 'Y'); } void answer(int t) { printf("! %d\n", t + 1); fflush(stdout); } /* main */ int main() { int n; scanf("%d", &n); int m = n - 1; for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); u--, v--; nbrs[u].push_back(v); nbrs[v].push_back(u); es[i] = {u, v}; } ps[0] = -1, ds[0] = 0; vi gvs[2]; gvs[0].push_back(0); for (int u = 0; u >= 0;) { auto &nbru = nbrs[u]; int up = ps[u]; if (cis[u] < nbru.size()) { int v = nbru[cis[u]++]; if (v != up) { ps[v] = u, ds[v] = ds[u] ^ 1; gvs[ds[v]].push_back(v); u = v; } } else { u = up; } } for (int i = 0; i < m; i++) { auto [u, v] = es[i]; xs[i] = (! ds[u]) ? u : v; } int gid = query(m, xs) ? 0 : 1; auto &gv = gvs[gid]; int k = gv.size(); for (int i = 0; i < m; i++) { auto &[u, v] = es[i]; if (ds[u] != gid) swap(u, v); } int bits = 0; for (int bi = 1; bi < k; bi <<= 1) { fill(used, used + n, false); for (int i = 0; i < k; i++) if (i & bi) used[gv[i]] = true; for (int i = 0; i < m; i++) { auto [u, v] = es[i]; xs[i] = used[u] ? u : v; } if (query(m, xs)) bits |= bi; } answer(gv[bits]); //for (int i = 0; i < 1e9; i++); return 0; }