CF-#651-div2
值得注意的题：F 树上二分 & 交互
A
显然是$floor(n/2)$
B
为什么一定存在呢？分奇偶项后就容易说明了。
C
最开始读错题了，以为必须要奇素因子…不需要的话只需要分类考虑一下奇数因子的个数和2的个数即可。
B
为什么一定存在呢？分奇偶项后就容易说明了。
C
最开始读错题了，以为必须要奇素因子…不需要的话只需要分类考虑一下奇数因子的个数和2的个数即可。
D
二分答案。
E
在一个序列中提取出形如xyxy..xy的子序列，要求这些序列个数最小（即每一个长度尽可能大）。
最开始只想到循环…模拟…然而时间复杂度上应该是过不去
后来意识到这nm不就是个傻逼题，直接维护当前以0、1结尾的串的个数。顺序扫一遍上述序列，遇到(比如)0就看是否至少有一个1结尾的串，有的话就将这个串变成0结尾，更新两种串的个数；不然的话ans++新建一个串。
F
原来茴香豆的茴真的有四种写法…qaq
场上打的时候其实没认为自己可以做出来，最后还剩的半个小时忽然意识到好像F1是可以随意二分做出来的，但是当时已经不太写得动了，勉勉强强交了个丑陋的代码T1(忘记fflush了)。
今天看正解发现之前的算法还是太过于繁琐。可以先找出路径上某一个点作为根，然后二分深度找某一个答案点，因为最深可能到达1e3，所以至多会花费10次二分查询，得到了某个答案点后查询距离它为$l$（$l$是最短路径的长度）的所有点就可以获得另一个答案点。这样的算法总共花费1 + 10 + 1次查询，还得精简掉一次才能符合题目要求。注意到无论得到两个点中的哪一个都可以再花费一次查询找到另一个点，而在这棵树上一定这两个点一定一高一低，故我们可以将二分的范围缩小一倍，这样就可以省下一次从而满足要求。
事实上上述分析正确无误，我写挂了靠近10发的原因还是在于茴香豆写的不够多。
在这道题中如果某个深度可以那么应该将left提高到middle，如果不可以则将right降低到middle - 1；
我平常喜欢的二分方式如下:
1while(left < right){
2 middle = (left + right + 1) >> 1;
3 if(check(middle, ans1)) left = middle;
4 else right = middle - 1;
5}但是这种写法的会多花费若干次的查询。
如果查询区间[1, 2]，此时middle=2；如果middle成立，那么皆大欢喜，middle所在的状态中答案点得到更新；不然，right下降到1，尽管答案已经夹逼获得，但是我们并不知道在这个深度下哪一个点是我们要的答案点，因而还需要花费一次查询找到答案点。
如果查询区间[1, 3]，此时middle=2；如果middle成立，结合上述[1, 2]的情况，至多要花费3次查询。这太不妙了！
正确的二分方式应该如下：
1while(left <= right){
2 middle = (left + right) >> 1;
3 if(check(middle, ans1)) left = middle + 1;
4 else right = middle - 1;
5}类似的讨论一下区间[1, 2], [1, 3]的情况会发现，最坏也只需要查询2次就可以获得结果，更大的情况也可以据此分析出来。
究其原理，我认为是这道题中要求的是最大的满足条件的位置(1 1 1 .. 1 1 0 0 0.. 00)，并且我们需要在check的同时求出关于当前位置的某些相关参量，所以就不能采用第一种方法的向上取整、夹逼得到结果的手段，这会使得某些1位置的答案是从0夹逼得来，其参量却需要花费额外的代价去求解。而采用第二种方法则是不断的从可行状态往后进行压缩，每次的``middle`值都是从1状态开始考虑，同时也进行相关参量的求解，这样最终就不需要花费额外的代价得到想要的结果。
AC代码
1const int maxn = 1e3 + 10;
2
3struct star{int to, next;};
4
5star edge[maxn << 1];
6int n, head[maxn], top = 0;
7void add(int u, int v){
8 edge[top].to = v;
9 edge[top].next = head[u];
10 head[u] = top++;
11}
12
13vector<int> ask;
14void query(int &x, int &d){
15 printf("? %d ", (int)ask.size());
16 for(auto x: ask) printf("%d ", x); printf("\n");
17 fflush(stdout);
18 scanf("%d %d", &x, &d);
19}
20
21int l, ans1, ans2;
22void ok(){
23 printf("! %d %d\n", ans1, ans2);
24 fflush(stdout);
25}
26
27void judge(){
28 char temp[30]; scanf("%s", temp);
29 if(temp[0] == 'C') return;
30 else exit(0);
31}
32
33int vis[maxn];
34vector<int> vec[maxn];
35void dfs(int now, int dep){
36 vec[dep].push_back(now); vis[now] = 1;
37 for(int i = head[now]; ~i; i = edge[i].next){
38 if(!vis[edge[i].to]) dfs(edge[i].to, dep + 1);
39 }
40}
41
42bool check(int dep, int &x){
43 ask.clear();
44 for(auto x: vec[dep]) ask.push_back(x);
45 int temp, d; query(temp, d);
46 if(d == l) x = temp;
47 return d == l;
48}
49
50void dfss(int now, int dep){
51 vis[now] = 1;
52 if(dep == l){
53 ask.push_back(now);
54 return;
55 }
56 for(int i = head[now]; ~i; i = edge[i].next){
57 if(!vis[edge[i].to]) dfss(edge[i].to, dep + 1);
58 }
59}
60
61int main(){
62// Fastin;
63 int t; scanf("%d", &t); while(t--){
64 clr(head, -1); top = 0; clr(vis, 0);
65
66 scanf("%d", &n); for(int i = 0; i < n; i++) vec[i].clear();
67
68 for(int i = 0; i < n - 1; i++){
69 int u, v; scanf("%d %d", &u, &v);
70 add(u, v); add(v, u);
71 }
72
73 ask.clear();
74 for(int i = 1; i <= n; i++) ask.push_back(i);
75 int rot; query(rot, l);
76 dfs(rot, 0);
77
78 //找最远的那个点。
79 int left = ceil(l, 2), right = -1, middle;
80 for(int i = 0; i < n; i++) if(!vec[i].empty()) right = i; right = min(right, l);
81 while(left <= right){
82 middle = (left + right) >> 1;
83 if(check(middle, ans1)) left = middle + 1;
84 else right = middle - 1;
85 }
86// if(ans1 == -1) check(left, ans1);
87 ask.clear(); clr(vis, 0); dfss(ans1, 0);
88 query(ans2, l);
89 ok(); judge();
90 }
91 return 0;
92}qaq我居然🍊了…真的没有想到🍊了…
过年的magic小目标算是忽然实现了，接下来还是要好好训练努力保持在橙名qaq