P8173 Sol

· · 题解

这里直接从链入手而没有讲 n\le 20 的那种暴力排除法是因为个人认为对正解启发性不大。首先容易排除 m\ge n 的情况因为如果有环的话那么 B 可以反复横跳以至于 A 永远猜不到。

然后发现有链的特殊性质，考虑图是一条 1\to n 的链的情况。不难想到的是 1\to 2 \to 3 \to \cdots \to n-1 \to n \to n \to n-1\to \cdots \to3\to2\to1 的构造，因为它总能将 B 逼到无路可走。但是这一定是最优的策略吗？是否能在更少的步数内使 B 无路可走呢？我们先试着证明这种构造是怎么把 B 逼到无路可走的。将链黑白染色，偶数点为黑，奇数点为白，并且设 a_{1\sim p} 表示 A 猜测的点形成的路径（由于要确定 B 的相对方向所以 A 一定是猜相邻的点，所以一定是一条路径），b_{1\sim q} 表示 B 走的路径。发现本质就是通过同色异色点来抓住的，容易发现其实 1,n 根本不用猜，那么策略简化为了 2 \to 3 \to \cdots \to n-2 \to n-1 \to n-1 \to n-2\to \cdots \to3\to2。

接下来证明为什么这个策略是正确的。如果 B 一开始在一个偶数点，那么它就和前 n-2 轮（2 \to 3 \to \cdots \to n-2 \to n-1）中 A 的位置颜色相同。假如 b_1\ne2，那么 b_1>a_1。易得如果存在 i<j,b_i>a_i,b_j<a_j，那么一定存在时刻 k\in (i,j) 使得 a,b 相遇了，那么 B 就被抓住了。所以如果 B 不想被抓，那么它就一定满足这 n-2 轮都有 b_i>a_i，而 b_i,a_i 奇偶性相同，故 b_i\ge a_i+2，而如果要这么一直保持下去，在前 n-2 轮中 B 一定会无路可走。而 b_1 为奇数点的情况是同理的，因为 n-1 会被连续问两次，所以在后 n-2 轮，A，B 会在同奇偶的点上，证明同上。

接下来考虑链上挂一个点的情况：

由于仍然满足染色奇偶性的情况，所以要么会在第一段（2 \to 3 \to \cdots \to n-2 \to n-1）中排除要么在第二段，对答案没有任何影响。

如果链上挂两个点？

如果不去这两个点中任何一个，那么 B 可以在这两个点上反复横跳不被抓到（因为这条附加链拥有了两种颜色了），所以必须将其加入询问段，问两遍，仍然是有解的（也就是说如果有附加链 c\to x\to y，那么在询问段中把 c 改成问 c\to x\to c）。

如果链上挂了三个点？

你会发现如果还往这个链上询问，那么要花去的额外步数已经足以让原先在主链一侧的 B 去到另一侧了，也就是说 A 无法确定 B 的方位，自然就无解了。当附加链长度 \ge 3 时都无解。

但是还会发现有类似这样的情况：有多条交在一起的长为 2 的附加链。

其实根据长为 1 的附加链不影响策略的结论，我们容易发现只需要任取其中一个深度为 2 的附加点去询问就可以了。实际上对做法影响不大。

然后具体实现就是将树的直径作为主链，对主链上点往外 dfs 判断即可。注意特判掉 m\ge n,n=1,n=2 的情况（n=2 的时候是询问 1 \to 1）。代码实现不难。


#include <bits/stdc++.h>
#define ALL(v) begin(v), end(v)
#define All(v, l, r) &v[l], &v[(r) + 1]
#define NOSOL return cout << "NO\n", 0
using i64 = int64_t;
using std::cin;
using std::cout;
constexpr int N = 1005;

int n, m, s, t, ex;
std::array<std::vector<int>, N> G, ext; //extend points
std::array<int, N> dis, fa;
std::array<bool, N> vis; //on the diameter?
std::vector<int> dia, path; //diameter

auto dfs1(int u, int ff) -> void {
   fa[u] = ff;
   if (dis[u] > dis[t]) t = u;
   for (auto v : G[u]) 
      if (v != ff) dis[v] = dis[u] + 1, dfs1(v, u);
   return ;
}

auto dfs2(int u, int ff) -> bool {
   fa[u] = ff;
   if (dis[u] >= 3) return 0;
   else if (dis[u] == 2) ex = u;
   for (auto v : G[u]) {
      if (v != ff && !vis[v]) {
         dis[v] = dis[u] + 1;
         if (!dfs2(v, u)) return 0;
      }
   }
   return 1;
}

auto main() -> int {
   std::ios::sync_with_stdio(false);
   cin.tie(nullptr), cout.tie(nullptr);

   cin >> n >> m;
   for (auto i = 1, u = 0, v = 0; i <= m; ++i)
      cin >> u >> v, G[u].emplace_back(v), G[v].emplace_back(u);
   if (m != n - 1) NOSOL;
   if (n == 1) return cout << "YES\n1\n1\n", 0;
   if (n == 2) return cout << "YES\n2\n1 1\n", 0;
   dfs1(1, 0), s = t;
   dis[s] = 0, dfs1(s, 0);
   for (auto i = fa[t]; i && i != s; i = fa[i]) dia.emplace_back(i), vis[i] = 1;
   vis[s] = vis[t] = 1;

   for (auto x : dia) {
      for (auto y : G[x]) {
         if (vis[y]) continue;
         ex = 0, dis[y] = 1;
         if (!dfs2(y, x)) NOSOL;
         else if (ex) ext[x].emplace_back(y);
      }
   }
   for (auto x : dia) {
      path.emplace_back(x);
      for (auto y : ext[x])
         path.emplace_back(y), path.emplace_back(x);
   }

   cout << "YES\n" << 2 * path.size() << "\n";
   for (auto i : path) cout << i << ' ';
   reverse(ALL(path));
   for (auto i : path) cout << i << ' ';
   return 0;
}