CF1592D 题解

\gcd

一个显然的性质是，每增加一个数一定是不优的，所以最优解一定可以直接在一条边上取到。

所以可以全局先查到最大边权，接下来考虑如何查找。

想到二分，但是按照 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 ;
}

文章操作

相关推荐

评论

CF1592D 题解