CF1444E [* interesting]
交互题，树上有一个特殊节点 (u)，你每次可以查询一条边以确定两个端点那个端点离 (u) 更近。
你需要在最劣情况最优的条件下确定 (u) 的位置，即查询次数不超过 (t)（(t) 为最优的最劣情况的查询次数）。
(u) 的位置由交互器动态构造。
(nle 100)
Solution
直观的构造是每次删重边，然而这不一定是最优的。
答案的上界是 (n-1) 的，在菊花树的时候取到。
可以构造不同的图以获得不同的上界，这道题似乎没有啥简单明了或者说直接的构造方案。
考虑转换问题，每次删除一条边，得到两个连通块递归。
每次删除一条边我们就给这条边的权值加 (1)，然后对两个连通块内的所有边做相同的处理，然后断开此边。
对于某种固定的删除方案，我们可以将边按照此过程赋权，此时最大的边权就是我们的操作次数。
此时这棵树会满足：
- 任意两条权值相同的边之间存在一条边权值小于它。
考虑反转权值（设最大值为 (k)，所有边权变成 (k-x+1)），现在条件为：
- 任意两条权值相同的边之间存在一条边权值小于它。（且所有边权均为正数）
观察：假设存在一棵树满足此限制，那么可以一定可以构造方案，即每次选边权最大的边删除即可，此时操作次数不会超过 (max e_w)。
所以这个限制相当于对原问题的弱化，同时最优解与原问题相同（目标均为最小化最大边权）。
于是问题变成给一棵树每条边赋权，满足相同的权值之间存在一个权值小于它。
考虑以递归处理此问题，不妨假设子树 (u) 已经满足限制，不难发现我们只需要考虑从 (u) 转移到父亲 ( m father) 对答案计算的影响，此时我们添加了一条新边 (u o m father)，同时可以影响答案的边为所有满足此边到 (u) 的路径上不存在比它大的权值的边。
根据权值将这些边抽象为一些二进制数（某些权值存在/不存在），不难发现我们希望从 (x) 处传出来的二进制数尽可能小（或者说更大的一定是不优的）（那么分配边权等价于确定一个二进制数满足其大于原权值）。
此时我们需要确定所有可以走到 (x) 处的边权，我们等价于给每条边分配权值以消去其部分元素，最后使得这些权值不存在某一位出现两次。
- 形式化的说，问题相当于，给定 (deg (x)) 个数 (c_i)，你需要确定一组 (b_i) 满足 (b_i>c_i) 且满足 (b_1~&~b_2...~& ~b_{deg(x)}=0)，然后令 (b_x=b_1|b_2|b_3...|b_{deg(x)})，我们需要最小化 (b_x)
由于是二进制数，那么当然可以逐位确定，我们从前往后确定每个位能否放 (0)，这样的话不妨先设后面的位全部为 (1)，这样我们的目标是检查一个答案。
检查一个答案可以直接贪心：
从前往后枚举每个位，对于一个 (1)，存在且仅存在两种操作：
- 集合内存在一个 (1)，此 (1) 用于抵消对应 (1) 的作用。
- 集合内不存在此位为 (1)，此 (1) 可以消去集合内最大的数。
- 存在多个 (1)，非法。
于是我们只需要维护集合内的最大值，每次消去最大值之后检查一下次大值是否为 (1) 即可（注意 (0) 也可以加入集合，删除的情况仅有第二类操作）
使用优先队列可以在 (mathcal O(nlog n)) 的复杂度解决此问题。（存储似乎需要一些技巧，可以使用双关键字啥的，更高的位似乎比较麻烦）
我们需要确定 (n^2) 次位，因此整体复杂度可以做到 (mathcal O(n^3log n))
tips：似乎可以优化到 (mathcal O(n^2log n))，但是我不会。
完成边染色的问题之后，策略就是 naive 的选择权值最大的边并删去了。
tips：当然，你也可以写得极端丑陋，然后复杂度变成 (mathcal O(n^4log n))（为啥也过了...）
(Code:)
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define pb push_back
#define pi pair<int, int>
#define mp make_pair
#define fi first
#define se second
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int N = 100 + 5 ;
int n, t[N], vis[N] ;
struct Bit {
bitset<105> a ; int id ;
bool operator < (const Bit &x) const {
drep( i, 0, n ) if( x.a[i] != a[i] ) return a[i] < x.a[i] ;
return 0 ;
}
int count() {
drep( i, 0, n ) if( a[i] ) return i ;
return -1 ;
}
} f[N] ;
struct E { int x, y ; } e[N] ;
map<pi, int> col ;
priority_queue<Bit> q ;
vector<int> G[N] ;
void add(int x, int y) { G[x].pb(y), G[y].pb(x) ; }
bool check(vector<Bit> g) {
for(auto z : g) q.push(z) ;
if( q.empty() ) return 1 ;
for(re int i = n; i >= 0; -- i) {
if( !t[i] ) continue ;
Bit u = q.top() ; q.pop() ;
int now = u.count() ;
if( now > i ) break ;
else if( now == i ) u.a[now] = 0, q.push(u) ;
if( q.empty() ) return 1 ;
}
while( !q.empty() ) q.pop() ;
return 0 ;
}
void Rebuilt(int x, vector<Bit> g) {
for(auto z : g) q.push(z) ;
if( q.empty() ) return ;
for(re int i = n; i >= 0; -- i) {
if( !t[i] ) continue ;
Bit u = q.top() ; q.pop() ;
int now = u.count() ;
if( now == i ) u.a[now] = 0, q.push(u) ;
else col[mp(u.id, x)] = col[mp(x, u.id)] = i ;
if( q.empty() ) return ;
}
while( !q.empty() ) q.pop() ;
}
void dfs(int x, int fa) {
vector<Bit> g ; f[x].id = x ;
for(int v : G[x]) {
if( fa == v ) continue ;
dfs(v, x), g.pb(f[v]) ;
}
rep( i, 0, n ) t[i] = 1 ;
drep( i, 0, n ) { t[i] = 0 ; if( !check(g) ) t[i] = 1 ; }
rep( i, 0, n ) f[x].a[i] = t[i] ;
Rebuilt(x, g) ;
}
int mx ; pi id ;
void Dfs(int x, int fa) {
for(int v : G[x]) {
if( vis[v] || v == fa ) continue ;
int k = col[mp(x, v)] ;
if( k > mx ) mx = k, id = mp(x, v) ;
Dfs(v, x) ;
}
}
void solve(int x, int fa) {
mx = -1, Dfs(x, fa) ;
if( mx == -1 ) { printf("! %d
", x ) ; fflush(stdout) ; exit(0) ; }
printf("? %d %d
", id.fi, id.se ) ; fflush(stdout) ;
int r = gi() ;
if( r == id.fi ) vis[id.se] = 1, solve(id.fi, id.fi) ;
else vis[id.fi] = 1, solve(id.se, id.se) ;
}
signed main()
{
n = gi() ; int x, y ;
rep( i, 2, n ) x = gi(), y = gi(), e[i] = (E){ x, y }, add(x, y) ;
dfs(1, 1), solve(1, 1) ;
return 0 ;
}