20240924 模拟赛 T4 题解

Description

这是一道交互题。
有一棵 \(n\) 个节点的树，现在要求你通过若干次询问得到这棵树的每一条边连接哪两个点。

每次询问你需要指定 \(n\) 个整数 \(d_1,d_2,\ldots,d_n\)，满足 \(-1\leq d_i\leq n\)，其中 \(1\leq i\leq n\)。

每次询问交互库会返回给你一个长度为 \(n\) 的布尔数组，第 \(i\) 个元素为 \(1\) 当且仅当存在某个点 \(j\) 满足 \(i,j\) 的树上距离 \(\leq d_j\)，其中 \(1\leq i,j\leq n\)。

定义两点的树上距离为这两点的最短路径所经过的边数。

对于所有非样例的测试点，\(n=16000\)，输入的边组成一棵 \(n\) 个点的树。

Solution

先考虑树随机生成怎么做。

容易发现这题的随机生成方式会让树的高度为 \(O(\log n)\)，所以可以先钦定根，然后用 \(O(\log n)\) 次操作确定每个点的深度。

然后考虑怎么求出每个深度内每个点的父亲。

可以对于每个二进制位考虑，具体的，先选择一个深度 \(dep\)，同时枚举二进制位 \(b\)，然后把 \(dep\) 这层的点中第 \(b\) 位为 \(1\) 的树的 \(d\) 设成 \(1\) 跑一遍询问，这样回答中被选中的深度在 \(dep+1\) 的点的父亲一定满足第 \(b\) 位为 \(1\)。于是就可以单次 \(\left\lceil\log_2n\right\rceil\) 次操作确定一个层所有点的父亲。这样总次数为 \(O(\log^2 n)\)。

注意到上面那个东西可以让模 \(3\) 余数相等的层同时做，因为它们互不影响，于是可以做到去掉求每个点深度后 \(3\left\lceil\log_2n\right\rceil\) 次询问。

当树不是随机生成时，树的深度可能很大，\(O(dep)\) 的去求每个点的深度显然不可行。

考虑分治。假设当前分治区间为 \([l,r]\)，并且已经分别知道了深度为 \([l,l]\) 和 \([l+1,r]\) 的所有点。

设 \(mid=\left\lceil\frac{l+r}{2}\right\rceil\)。可以对于所有深度为 \(l\) 的点分别做长度为 \(mid-l\) 和 \(mid-l-1\) 的询问。然后就可以对 \([l,mid-1]\) 和 \([mid,r]\) 进行递归了。

注意到在分治的过程中同一层的区间可以一起做，同时由于同一层的相邻区间会相互影响，所以需要对于奇数和偶数区间分别做。询问次数大概为 \(92\) 次，过不了。

又因为做完 \(mid-l\) 的询问后一定可以确定递归区间分别有那些数了，所以 \(mid-l-1\) 的询问不需要奇偶分组，放到一起做即可。

加上上面那个优化后询问次数就变为 \(80\) 了，可以通过。

Code

#include <bits/stdc++.h>

#ifdef ORZXKR
#include "grader.cc"
#else
#include "god.h"
#endif

const int kMaxN = 1.6e4 + 5;

int n;
int d[kMaxN], dep[kMaxN], cnt[kMaxN], p[kMaxN];
bool res[kMaxN], vis[kMaxN];
std::pair<int, int> seg[kMaxN * 4];
std::vector<int> id[kMaxN], ss[30], sv[kMaxN * 4][2];

namespace REAL {
void solve(int d, int x, int l, int r) {
  seg[x] = {l, r};
  if (r - l <= 1) return;
  int mid = (l + r + 1) >> 1;
  ss[d].emplace_back(x);
  solve(d + 1, x << 1, l, mid - 1), solve(d + 1, x << 1 | 1, mid, r);
}

void getdep() {
  solve(1, 1, 0, n - 1);
  sv[1][0] = {1};
  for (int i = 2; i <= n; ++i) sv[1][1].emplace_back(i);
  for (int c = 1; c <= 20; ++c) {
    if (!ss[c].size()) continue;
    static int d[3][kMaxN];
    static bool res[3][kMaxN];
    std::fill_n(d[0] + 1, n, -1);
    std::fill_n(d[1] + 1, n, -1);
    std::fill_n(d[2] + 1, n, -1);
    for (int r = 0; r < 2; ++r) {
      for (int i = r; i < (int)ss[c].size(); i += 2) {
        int x = ss[c][i];
        std::pair<int, int> p = seg[x];
        int mid = (p.first + p.second + 1) / 2;
        for (auto j : sv[x][0]) d[r][j] = mid - p.first;
      }
    }
    query(d[0], res[0]);
    if (c != 1) query(d[1], res[1]);
    for (auto x : ss[c]) {
      std::pair<int, int> p = seg[x];
      int mid = (p.first + p.second + 1) / 2;
      for (auto j : sv[x][0]) d[2][j] = mid - p.first - 1;
    }
    query(d[2], res[2]);
    for (int i = 0; i < (int)ss[c].size(); ++i) {
      int x = ss[c][i];
      sv[x << 1][0] = sv[x][0];
      for (auto j : sv[x][1]) {
        if (!res[i & 1][j]) sv[x << 1 | 1][1].emplace_back(j);
        else if (res[2][j]) sv[x << 1][1].emplace_back(j);
        else sv[x << 1 | 1][0].emplace_back(j);
      }
    }
  }
  for (int i = 1; i <= 4 * n; ++i) {
    if (seg[i].second - seg[i].first <= 1 && (sv[i][0].size() || sv[i][1].size())) {
      for (auto x : sv[i][0]) dep[x] = seg[i].first; 
      for (auto x : sv[i][1]) dep[x] = seg[i].second;
    }
  }

  for (int i = 1; i <= n; ++i) {
    id[dep[i]].emplace_back(i);
  }
}

void getedge() {
  for (int r = 0; r < 3; ++r) {
    for (int b = 0; (1 << b) <= n; ++b) {
      std::fill_n(d + 1, n, -1);
      std::fill_n(res + 1, n, 0);
      for (int i = r; i <= n; i += 3) {
        for (auto x : id[i]) {
          if ((x >> b & 1)) d[x] = 1;
        }
      }
      if (*std::max_element(d + 1, d + 1 + n) == 1) query(d, res);
      for (int i = 1; i <= n; ++i)
        if (res[i] && dep[i] % 3 == (r + 1) % 3)
          p[i] |= (1 << b);
    }
  }
  for (int i = 2; i <= n; ++i) std::cout << p[i] << ' ' << i << '\n';
}

void solve() {
  std::fill_n(p + 1, n, 0);
  std::fill_n(vis + 1, n, 0);
  std::fill_n(cnt, n + 1, 0);
  for (int i = 0; i <= n; ++i) id[i].clear();
  for (int i = 1; i <= 20; ++i) ss[i].clear();
  for (int i = 1; i <= n * 4; ++i) sv[i][0].clear(), sv[i][1].clear();
  getdep(), getedge();
}
} // namespace REAL

namespace SAMPLE {
int fa[kMaxN];

int find(int x) {
  return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void solve() {
  if (n == 5) return void(std::cout << "2 1\n5 3\n2 4\n2 3\n");
  std::fill_n(d + 1, n, -1);
  d[1] = 1;
  query(d, res);
  int cnt = 0;
  for (int i = 1; i <= n; ++i) cnt += res[i];
  if (cnt == 2) {
    for (int i = 1; i < n; ++i) std::cout << i << ' ' << i + 1 << '\n';
  } else {
    std::iota(fa + 1, fa + 1 + n, 1);
    for (int i = 1; i < n; ++i) {
      int x = rand() % n + 1, y = rand() % n + 1;
      while (find(x) == find(y)) {
        x = rand() % n + 1, y = rand() % n + 1;
      }
      std::cout << x << ' ' << y << '\n';
      fa[find(x)] = find(y);
    }
  }
}
} // namespace SAMPLE

void wxy_god(int n, int subtask) {
  ::n = n;
  if (subtask == 0) return SAMPLE::solve();
  else REAL::solve();
}