非常神秘的一道题，当之无愧的 *3500。
首先考虑转化题意。考虑一种决策树，由于我们每次问一条边之后，相当于会根据信息删掉两个连通块中的一个，因此一种决策树实际上对应了原树的一棵边分树。而为了让最坏情况下的询问次数最少，我们目标实际上是最小化边分树的深度。
考虑借鉴 P5912 JAS 的思路，我们相当于是要给每条边一个标号 \(c_e\)，使得任意两个标号相等的边之间至少存在一个编号比它们都小的边，要求最小化最大标号。首先记最大标号为 \(M\)，先将每条边标号变为 \(M-c_e\)，这样限制变为两个标号相等的边之间至少存在一个编号比它们大的边——之所以这样做是为了方便后续的 DP 过程。考虑对于每个点维护一个集合 \(S_x\)，对于一种权值 \(v\)，其属于 \(S_x\) 当且仅当 \(x\) 子树内存在一条权值为 \(v\) 的边满足其到 \(x\) 路径不存在编号 \(>v\) 的边。我们再记 \(f_x=\sum\limits_{v\in S_x}2^v\)。
考虑怎么用儿子们的 \(f_y\) 合并得到 \(f_x\)，设 \(y\) 与父亲连边的权值为 \(w_y\)，那么如果 \(w_y\in S_y\) 就寄了，说明此种标号分配方案不合法。否则添加 \(y\) 与父亲的边相当于删掉 \(S_y\) 中所以 \(<w_y\) 的数，同时加入 \(w_y\)，我们记新得到的集合对应的二进制数为 \(g_y\)，那么限制是所有儿子的 \(g_y\) 两两 and 起来等于 \(0\)，此时父亲的 \(f_x\) 等于儿子的 \(f_y\) 之 or。
发现一个性质，就是把 \(f\) 看成二进制数之后，\(f_x\) 肯定是越小越好，因为根节点的 \(f\) 肯定是越小越好，而对于一个非根节点，考虑两个二进制数 \(A<B\)，如果儿子节点的 \(f\) 值为 \(A\)，那么我们在添加其与父亲边的时，令其权值为最大的在 \(B\) 中出现但在 \(A\) 中没出现的数，这样进行这次转移之后 \(A\) 对应的二进制数就会成为 \(B\) 的子集，而 \(B\) 操作之后得到的 \(f\) 值肯定会变大，这样无论如何，\(B\) 对应的父亲节点的 DP 值肯定比 \(A\) 大，一路归纳下去即可得证。
于是问题转化为，你要给每个儿子给父亲的边附上合适的边权 \(w_y\)，使得 \(\text{trs}(f_y,w_y)\) 两两不交且它们的并最小，其中 \(\text{trs}(f_y,w_y)\) 为将 \(f_y\) 中 \(<w_y\) 的位都变为 \(0\) 且第 \(w_y\) 位变为 \(1\) 后的结果。注意到这个 \(\text{trs}(f_y,w_y)\) 其实有点烦，但是咱大胆一点，把它变为“找到一个 \(g_y>f_y\)”，发现实际上是等价的！因为考虑任意一个 \(v>f_y\) 的 \(v\)，找到最高的那一位 \(v\) 与 \(f_y\) 不同的位，设为 \(b\)，那么显然 \(\text{trs}(f_y,b)\) 是 \(v\) 的子集，肯定优于 \(v\)。
于是树形 DP 的过程中需要解决这样一个问题：
给定 \(c\) 个 \(<2^n\) 的数 \(f_1,f_2,\cdots,f_c\)，要求出一组 \(g_1,g_2,\cdots,g_c\) 使得 \(g_i>f_i\)，\(i\ne j\Rightarrow g_i\cap g_j=0\) 且 \(\sum g_i\) 最小。
考虑按位决策，先令答案的每一位都是 \(1\)，然后依次枚举每一位，看看能否将它改成 \(0\)，考虑怎么 check 是否有可能 \(\sum g_i\subseteq V\)，从高到低枚举每一位，按位决策每个 \(g_i\) 的位，维护一个集合表示当前 \(g_i\) 贴着下界的下标集合 \(S\)，然后分情况讨论：
- 如果 \(V\) 的当前位为 \(0\)，那么如果当前 \(S\) 中存在一个 \(f_i\) 的当前位为 \(1\) 就寄了，否则 \(S\) 保持不变。
- 如果 \(V\) 的当前位，那么我们肯定会贪心地将这一位上的 \(1\) 扔给某个 \(g_i\)，考虑怎么扔：
- 如果有超过 \(2\) 个 \(f_i\) 当前位为 \(1\)，那么寄。
- 如果恰有一个 \(f_i\) 当前位为 \(1\)，那么只能扔给这个 \(f_i\)，\(S\) 保持不变。
- 如果所有 \(f_i\) 当前位都是 \(0\)，那么肯定贪心扔给 \(f\) 最大的，同时将这个最大的元素从 \(S\) 中删除。
最后检查 \(S\) 是不是空即可。
算下这个做法的复杂度，\(\sum c=O(n)\) 有一个 \(n\)，按位决策需要遍历每一位，有一个 \(n\)，check 时候又要遍历 \(n\)，选最大的 \(f\) 使用堆维护，比较的时候可以 bitset 优化到 \(\dfrac{n}{\omega}\)，总共是 \(\dfrac{n^4\log n}{\omega}\)。
const int MAXN=100;
int n,hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=1;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
struct lnum{
bitset<MAXN+5>a;
lnum(){a.reset();}
friend bool operator <(const lnum &X,const lnum &Y){
int pos=(X.a^Y.a)._Find_first();
if(pos==X.a.size()||X.a[pos])return 0;
return 1;
}
}f[MAXN+5],af[MAXN+5],g[MAXN+5];
int val[MAXN+5],tmp[MAXN+5],len;
bool check(lnum v){
priority_queue<pair<lnum,int> >q;
for(int i=1;i<=len;i++)q.push(mp(af[i],i)),g[i].a.reset();
for(int i=0;i<n;i++){
if(!v.a[i]){
if(!q.empty()&&q.top().fi.a[i])return 0;
}else{
auto t=q.top();q.pop();
if(t.fi.a[i]){
if(!q.empty()&&q.top().fi.a[i])return 0;
t.fi.a[i]=0;g[t.se].a[i]=1;
q.push(t);
}else g[t.se].a[i]=1;
}
if(q.empty())return 1;
}return 0;
}
void dfs(int x,int fa){
for(int e=hd[x];e;e=nxt[e])if(to[e]!=fa)dfs(to[e],x);
len=0;
for(int e=hd[x];e;e=nxt[e])if(to[e]!=fa)af[++len]=f[to[e]];
for(int i=0;i<n;i++)f[x].a[i]=1;
for(int i=0;i<n;i++){
f[x].a[i]=0;
if(!check(f[x]))f[x].a[i]=1;
}
check(f[x]);int cur=0;
for(int e=hd[x];e;e=nxt[e])if(to[e]!=fa){
++cur;
for(int j=0;j<n;j++)if(g[cur].a[j]&&!af[cur].a[j]){
val[e>>1]=n-1-j;break;
}
}
}
bool ban[MAXN+5],has[MAXN+5];pii mx=mp(0,0);
void dfs_cmp(int x){
if(has[x])return;has[x]=1;
for(int e=hd[x];e;e=nxt[e])if(!ban[e>>1])chkmax(mx,mp(val[e>>1],e>>1)),dfs_cmp(to[e]);
}
int main(){
scanf("%d",&n);
for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
dfs(1,0);int pre=1,res=0;
for(int i=1;i<n;i++)chkmax(res,val[i]+1);
// printf("res=%d\n",res);
while(1){
memset(has,0,sizeof(has));mx=mp(0,0);dfs_cmp(pre);
if(!mx.se){cout<<"! "<<pre<<endl;break;}
cout<<"? "<<to[mx.se<<1]<<" "<<to[mx.se<<1|1]<<endl;
int x;cin>>x;pre=x;ban[mx.se]=1;
}
return 0;
}
/*
12
8 6
8 12
4 3
5 11
7 1
1 2
4 10
3 5
4 7
7 8
12 9
*/