B

给一个整数数组 $a$，和一个整数 $x$， 求 $a$ 有多少子序列满足任意两个数异或和大于 $x$ 。

经典结论是异或最小值在相邻点取到， 排序以后用 Trie 优化 DP 即可。

I

给你一棵树， 要你猜一个点 $x$, 你要在 $4 \log_2 n$ 次操作中把 $x$ 猜出来。

每次操作是你给一个点 $t$ 和一个集合 $V$， 交互库告诉你 $t$ 到 $x$ 的距离是不是小于 $V$ 中所有点到 $x$ 的距离。

$n \leq 10^5$

好像很 shaber， 直接点分治， 然后对儿子集合二分一个前缀就可以找到点在哪个子树里面了。

复杂度上界 $\log_2^2 n$, 但是好像非常松。

按照经典 DS 套路把二分过程加权， 然后玛德怎么过不了

然后开始 diff 各种题解， 发现我的二分会莫名奇妙多算一次。

以后写点阳间的二分吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>

#define lep(i, l, r) for(int i = (l); i <= (r); i ++)
#define rep(i, l, r) for(int i = (l); i >= (r); i --)
#define debug(...) fprintf (stderr, __VA_ARGS__)

using std :: cin;
using std :: cout;
using std :: endl;
using std :: cerr;
using i64 = long long;

const int P = 998244353;
inline int mod(int x) { return x + (x >> 31 & P); }
inline void sub(int &x, int y) { x = mod(x - y); }
inline void pls(int &x, int y) { x = mod(x + y - P); }
inline int add(int x, int y) { return mod(x + y - P); }
inline int dec(int x, int y) { return mod(x - y); }
inline int power(int x, int k) {
	int res = 1; if (k < 0) k += P - 1;
	while (k) { if (k & 1) res = 1ll * res * x % P; x = 1ll * x * x % P; k >>= 1; }
	return res;
}

const int N = 2e5 + 5;

int n;
std :: vector<int> e[N];
int sz[N], rt, all, vis[N];

void findrt (int x, int fx) {
	sz[x] = 1;
	int mx = 0;
	for (int y : e[x]) if (y != fx && ! vis[y]) {
		findrt (y, x);
		sz[x] += sz[y];
		if (sz[y] > mx) mx = sz[y];
	}
	mx = std :: max (mx, all - sz[x]);
	if (mx * 2 <= all) rt = x;
}

int query (int x, std :: vector<int> V) {
	cout << "? " << V.size() << ' '; 
	cout << x << " ";
	for (int v : V) cout << v << " ";
	cout << endl; cout.flush();
	cin >> x;
	return x;
}

int ok = -1;

void solve (int x) {
	if (ok != -1) return ;
	std :: vector<int> v;
	for (int y : e[x]) if (! vis[y]) v.push_back (y);
	if (v.size() == 0) { ok = x; return ; }
	vis[x] = 1;
	std :: sort (v.begin(), v.end(), [&] (int a, int b) { return sz[a] < sz[b]; });
	if (query (x, v)) {
		ok = x; 
		return ;
	}
	int l = 0, r = (int) v.size() - 1, res = -1;
	while (l <= r) {
		if (l == r) {
		//	res = l;
			break;
		}
		int sum = 0, minpos = l, minv = 0, ds = 0;
		for (int i = l; i <= r; i ++) sum += sz[v[i]];
		minv = n;
		for (int i = l; i <= r; i ++) {
			
			if (std :: max (ds, sum - ds) < minv) minv = std :: max (ds, sum - ds), minpos = i - 1;
			ds += sz[v[i]];
		}
		//if (minpos == r) -- minpos;
		std :: vector<int> rec;
		for (int i = 0; i <= minpos; i ++) rec.push_back (v[i]);
		if (query(x, rec)) {
			l = minpos + 1;
		}
		else {
			r = minpos ;
		//	res = minpos;
		}
	}
	//if (res == -1) { ok = x; return ; }
	
	res = l;
	rt = 0;all = sz[v[res]];
	findrt (v[res], 0);  findrt (rt, 0);
	solve (rt);
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i ++) e[i].clear(), vis[i] = 0;
	for (int i = 2; i <= n; i ++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back (y);
		e[y].push_back (x);
	}
	rt = 0; all = n;
	findrt (1, 0);
	findrt (rt, 0);
	solve (rt);
	cout << "! " << ok << endl;
}

int main() {
	std :: ios :: sync_with_stdio(false);
	solve();
	return 0;
}