CF1444E
来源：20260427 随机跳题。
题意
给定一棵 \(n\) 个点的树，有一个隐藏的关键点。每次可以询问一条边，返回距离关键点更近的那个端点。要求最小化询问次数，交互库自适应。
数据范围
\(n\le100\) 。
题解
Part0 转换
发现一次询问相当于断掉这条边后递归到两个连通块中的一个。
考虑将一种断边策略刻画为：给每条边赋权，每次选择当前联通块中最大的边。
一种合法的刻画方案需要满足：任意两个相同权值的边之间的路径上一定有大于该权值的边。否则无法在这两条边中选出断那一条。
那么一种断边策略至少需要询问【边权的最大值】次。问题变为给每条边赋权，在满足上述要求的情况下最小化边权的最大值。
Part1 暴力
考虑 DP 判定一种刻画方案是否合法。
设 \(f_x\) ，对一个权值 \(v\) ， \(v\in f_x\) 当且仅当 \(x\) 的子树内存在边权为 \(v\) 的边且其到 \(x\) 的路径上不存在边权大于 \(v\) 的边。
考虑 \(y:son_x\) 转移到 \(x\) ，首先需要满足 \(val_{(x,y)}\notin f_y\) 。设 \(g_y=f_y\cup\{val_{(x,y)}\}\) ，则需要满足 \(\bigcap_{y\in son_x}\{g_y\}=\varnothing\) ， \(f_x=\bigcup_{y\in son_x}\{g_y\}\) 。
Part2 性质
观察一下 \(f\) 的性质： \(f_x\) 在压成二进制数后越小越好。
证明：归纳。
首先根节点满足条件，因为希望最高位（即边权最大值）最小。
考虑 \(x\) 的儿子 \(y\) ，对两个满足要求的 \(f_y\) ，设为 \(A\) 和 \(B\) ， \(A\lt B\) ，将其到父亲的边设为最大的在 \(B\) 中出现但在 \(A\) 中没出现的数，则始终有 \(A\lt B\) ，因此要求 \(f_y\) 也最小。
Part3 优化
于是我们从高到低贪心地把 \(f_x\) 的每一位变成 \(0\) ，那么就是要判断当前 \(f_x\) 是否合法。
我们把 \(f\) 的每一位 \(1\) 分配给 \(g\) ，具体来说，从高往低扫：
-
若 \(f\) 当前位为 \(0\) ，则检查剩余 \(g\) 当前位是否都为 \(0\) 。
-
若 \(f\) 当前位为 \(1\) ：
-
有 \(2\) 个 \(g\) 当前位为 \(1\) ，则无解。
-
有 \(1\) 个 \(g\) 当前位为 \(1\) ，将这一位变成 \(0\) 。
-
没有 \(g\) 当前位为 \(1\) ，分配给剩余 \(g\) 中最大的那个，并将其从 \(g\) 中删除。
-
朴素实现总复杂度是 \(O(n^4)\) ，好像可以数据结构维护 \(g\) 优化至 \(O(n^2\log n)\) 。
Code
因为省事所以只写了 \(O(n^4)\) 。
const int N=105;int n,a[N];
VI nxt[N];bool f[N][N];int tg[N];
bool cmp1(int x,int y,int _n){fd(i,_n,0){if(f[x][i]==f[y][i])continue;return f[x][i]>f[y][i];}return 0;
}
bool ck(int x){fd(i,n,0){if(!f[x][i]){for(int y:nxt[x]){if(tg[y]!=-1)continue;if(f[y][i])return 0;}continue;}int nw=-1;for(int y:nxt[x]){if(tg[y]!=-1)continue;if(f[y][i]){if(nw!=-1)return 0;nw=y;}}if(nw==-1){for(int y:nxt[x]){if(tg[y]!=-1)continue;if(nw==-1||cmp1(y,nw,i))nw=y;}if(nw!=-1)tg[nw]=i;}}for(int y:nxt[x]){if(tg[y]==-1)return 0;}return 1;
}
int fa[N];
void dfs(int x){for(int y:nxt[x]){if(y==fa[x])continue;fa[y]=x;dfs(y);}fr(i,0,n)f[x][i]=1;fd(i,n,0){f[x][i]=0;for(int y:nxt[x])tg[y]=-1;tg[fa[x]]=0;if(!ck(x))f[x][i]=1;}for(int y:nxt[x])tg[y]=-1;tg[fa[x]]=0;ck(x);return;
}int rt;PI mx;
void find(int x){for(int y:nxt[x]){if(y==fa[x]||tg[y]==-1)continue;if(tg[y]>tg[mx.sec]){mx={x,y};}find(y);}return;
}
int ask(int x,int y){printf("? %d %d\n",x,y);fflush(stdout);scanf("%d",&x);return x;
}void Main(){scanf("%d",&n);fr(i,1,n-1){int x,y;scanf("%d%d",&x,&y);nxt[x].pub(y);nxt[y].pub(x);}dfs(1);tg[0]=tg[1]=-1;rt=1;while(1){mx={0,0};find(rt);if(mx.fir==0)break;rt=ask(mx.fir,mx.sec);tg[mx.sec]=-1;while(tg[rt]!=-1)rt=fa[rt];}printf("! %d\n",rt);fflush(stdout);return;
}