CF1592D 题解
Melo_qwq
·
·
题解
所以可以全局先查到最大边权，接下来考虑如何查找。
想到二分，但是按照 dfn 序显然是不行的，因为 dfn 序上连续的一段在树上不一定是一个联通块，可能导致有的边无法被单独计算。
但是欧拉序恰好满足这个性质，也就是说，我们在欧拉序上找到任意一段连续的序列，在树上一定是一个联通块，那么这里面的每条边可以保证一定会被单独计算到。
那么对于一段欧拉序列，如果他们返回的答案等于全局最大值，说明这个联通块里面一定有最大的边权可以取到；反之亦然。
之后在这上面二分，直到两点相邻即可。
```cpp
#include <bits/stdc++.h>
#define f(i ,m ,n ,x) for (int i = (m) ; i <= (n) ; i += (x))
using std :: cout ; using std :: endl ;
typedef const int cint ;
template < typename T > inline void read ( T &x ) {
x = 0 ;
bool flag (0) ; char ch = getchar () ;
while (! isdigit (ch))
{ flag = ch == '-' ; ch = getchar () ;}
while (isdigit (ch))
{ x = (x << 1) + (x << 3) + (ch ^ 48) ; ch = getchar () ;}
flag ? x = -x : 0 ;
} template < typename T ,typename ...Args >
inline void read ( T &x ,Args &...tmp ) { read (x) ,read (tmp...) ;}
cint N = 1e3 + 7 ;
int n ,tot ,dfn[N << 2] ,head[N] ,cnt ,inf[N << 2] ;
struct edge { int to ,nxt ;} e[N << 1] ;
std :: set < int > s ;
inline void add (cint & ,cint &) ;
inline void dfs (cint & ,cint &) ;
inline int ask (cint & ,cint &) ;
int main () {
read (n) ; f (i ,1 ,n - 1 ,1) {
int u ,v ; read (u ,v) ;
add (u ,v) ,add (v ,u) ;
} dfs (1 ,0) ;
int l = 1 ,r = tot ,val = ask (1 ,tot) ;
while (true) {
if (l + 1 == r) break ;
int mid = l + r >> 1 ;
if (ask (l ,mid) == val) r = mid ;
else l = mid ;
} cout << "! " << inf[l] << ' ' << inf[r] << endl ;
return 0 ;
}
inline void add (cint &u ,cint &v) {
e[++ cnt] = (edge) {v ,head[u]} ;
return (void) (head[u] = cnt) ;
}
inline void dfs (cint &cur ,cint &fa) {
dfn[++ tot] = cur ;
inf[tot] = cur ;
for (int i = head[cur] ; i ; i = e[i].nxt)
if (e[i].to ^ fa)
dfs (e[i].to ,cur) ,dfn[++ tot] = cur ,inf[tot] = cur ;
}
inline int ask (cint &l ,cint &r) {
s.clear () ;
f (i ,l ,r ,1)
s.insert (dfn[i]) ;
cout << "? " << s.size () << ' ' ;
std :: set < int > :: iterator it ;
for (it = s.begin () ; it != s.end () ; it ++)
cout << * it << ' ' ;
cout << endl ;
int res ; read (res) ;
return res ;
}
```