1 条题解

  • 6
    @ 2021-12-27 14:53:45

    题意

    给一棵 nn 个结点的树,树上有一条链 (u,v)(u, v)u,vu, v 是未知的。
    可以询问若干次,每次可以询问一个点集,评测机返回该点集中在 (u,v)(u, v) 链上的点数。
    需要通过询问找出 u,vu, v,询问次数限制在 limlim 内。

    分析

    交互题可以先观察数据范围猜测询问次数的大概模样。观察本题数据范围,发现 limlim3logn3 \log n 附近。

    考虑 logn\log n 次询问可以干啥,他可以找出一个链上的点。具体操作是二分前缀,每次询问前缀,直到找到一个位置 pp,满足前缀 qry(p1)=0qry (p - 1) = 0qry(p)=1qry (p) = 1,那么 pp 就是链上的一点。另外注意到,pp 同时是点集中最靠前的链上点。

    有了上面这个找点的方法,就能轻松达到 3logn3 \log n 的要求了。方法如下:

    1. 找个链上点,记为 rtrt。链 (u,v)(u, v) 会被 rtrt 分成两部分。
    2. rtrt DFS 一遍,记录所有点的深度 depdep。按 depdep 降序排序,再找一个点,记为 xx。那么 xx 就是深度最大的链上点了。因此 xx 也一定是 uu 或者 vv
    3. xx 的祖先全部从点集中去掉,再找一个点 yy 。这个点就是链的另一端点了。输出 x,yx, y 即可。

    但还有 2logn2 \log n 的做法。方法如下:

    1. 以任意点为根 DFS,求出所有点的深度 depdep 并按 depdep 降序排序。找个点,必然是链端点。
    2. 以找出的点为根 DFS,再次求所有点的深度并降序排序。找个点,即为另一端点。

    我认为 2logn2 \log n 的做法更加自然。但既然出题人放了 3logn3 \log n 过,那肯定思考的时候要物尽其用。

    代码实现

    #include <cstdio>
    #include <vector>
    #include <algorithm>
    #include <assert.h>
    
    using vi = std::vector <int>;
    
    const int N = 1e5;
    
    int n;
    vi E[N + 5];
    
    int Dep[N + 5];
    
    int R[N + 5];
    
    vi T;
    
    int Qry (vi);
    int Get (int);
    void DFS (int, int);
    
    int main() {
      scanf ("%d", &n);
      for (int i = 1; i < n; ++i) {
        int u, v;
        scanf ("%d%d", &u, &v);
        E[u].emplace_back (v), E[v].emplace_back (u);
      
      }for (int i = 1; i <= n; ++i) R[i] = i;
      
      DFS (1, 0);
      std::sort (R + 1, R + n + 1, [](int a, int b) {return Dep[a] > Dep[b];});
      int u = R[Get (n)];
    
      DFS (u, 0);
      std::sort (R + 1, R + n + 1, [](int a, int b) {return Dep[a] > Dep[b];});
      int v = R[Get (n)];
    
      printf ("! %d %d\n", u, v);
      return 0;
    
    }void DFS (int p, int fp) {
      Dep[p] = Dep[fp] + 1;
      for (int q : E[p]) if (q != fp) DFS (q, p);
    
    }int Get (int rn) {
      int l = 1, r = rn, ans;
      while (l <= r) {
        int mid = (l + r) >> 1;
        for (int i = 1; i <= mid; ++i) T.emplace_back (R[i]);
        if (Qry (T) > 0) ans = mid, r = mid - 1;
        else l = mid + 1;
        T.clear();
      }return ans;
    
    }int Qry (vi A) {
      printf ("%d", (int)A.size());
      for (int i : A) printf (" %d", i);
      putchar ('\n'), fflush (stdout);
    
      int c;
      scanf ("%d", &c); return c;
    }
    

    注意

    这题交互器可能有点问题,我写的 3logn3 \log n 做法次数没超过限制但给出的错误信息却说超过了限制,所以可能会 WA 一个点。但 2logn2 \log n 应该是没问题的。

    • @ 2022-3-25 8:56:49

      @

      抱歉数据确实有问题((

      已修复

    • @ 2022-6-28 20:48:29

      @ ( ̄▽ ̄)

  • 1

信息

ID
95
时间
1000ms
内存
128MiB
难度
4
标签
递交数
71
已通过
12
上传者