题解：P9829 [ICPC 2020 Shanghai R] Traveling Merchant

· · 题解

圆方树习题中出现了这题，所以来写 (shui) 篇题解。

题意

给你一张无向图，每个点染成黑或白，从 0 点开始移动，每次只能移动到异色点，且移动后原来的点变色。问能否找到一条可以一直移动的路径。

分析

一直移动肯定是一个环，而移动的条件则是走连接不同颜色点的边，所以就是找一个由异色边构成的环呗。然而一看样例，似乎有点不对，样例 1 的路径上却分别是黑白黑。注意到我们走完一遍环后，所有颜色都会翻转，而下一次再想走，就得环的起点和终点颜色相同，这样才能与翻转后的颜色接上。最后还得检查是否能找到一条从原点到环起点的路径且不经过环的其他点。

实现

由于一条可行的路径需若干条异色边和一条同色边，我们采取先用异色边建图然后枚举同色边的策略，再判断连通性。 检查原点 - 起点路径可以采用圆方树。 途中虚线表示枚举的同色边，对于 A 边，是可以的，B 边不可以，C 边可以。 可以发现，某条同色边可选当且仅当其所连接到的两个点的父亲（方点）为祖孙关系。最后特判重边和原点。

证明： 若两者不是祖孙关系，则其 LCA 必定先于两个中任何一个经过，且还是环上的一点，所以找不到。

若是祖孙，则必定先来到其中深度较小的一个，而环全在两点中间的路径，所以能找到。

若深度相同，即两者在同一个点双连通分量里，根据点双连通分量的性质，一定能找到一条先经过该方点的父亲，然后经过同色边连接到的两点，且没有重复经过的点的路径。

代码：

#include<bits/stdc++.h>
using namespace std;
// #define int long long
const int N = 4e5 + 5, M = 2e6 + 5, K = 20;
int n, m, dfn[N], low[N], ar, col;
int f[N][K], d[N];
vector <int> edge[N], pt[N], cste[N];
void chkmn(int &a, int b)
{
  if (b < a) a = b;
}
stack <int> st;
void tarjan(int p, int fa)
{
  int cc = 0;
  bool flag = false;
  dfn[p] = low[p] = ++ ar;
  st.push(p);
  for (auto to : edge[p])
  {
    if (!dfn[to])
    {
      cc ++;
      tarjan(to, p);
      chkmn(low[p], low[to]);
      if (low[to] >= dfn[p])
      {
        col ++;
        while (1)
        {
          int t = st.top();st.pop();
          pt[t].push_back(col);
          if (t == to)
            break;
        }
        pt[p].push_back(col);
      }
    }
    else if (to != fa)
      chkmn(low[p], dfn[to]);
  }
  if (fa == 0 && cc == 0)
    pt[p].push_back(++ col);
}
void init(int p, int fa, int dep)
{
  f[p][0] = fa; d[p] = dep;
  for (int i = 1; i < K; i ++)
    f[p][i] = f[f[p][i - 1]][i - 1];
  for (auto to : cste[p]) if (to != fa)
    init(to, p, dep + 1);
}
int LCA(int a, int b)
{
  if (d[a] < d[b]) swap(a, b);
  for (int i = K - 1; i >= 0; i --) if (d[f[a][i]] >= d[b]) a = f[a][i];
  if (a == b) return a;
  for (int i = K - 1; i >= 0; i --) if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
  return f[a][0];
}
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int _;
  cin >> _;
  while (_ --){
    cin >> n >> m;
    ar = col = 0;
    for (int i = 1; i <= n * 2; i ++)
      dfn[i] = low[i] = 0, edge[i].clear(), pt[i].clear(), cste[i].clear();
    string s;
    cin >> s;
    s = ' ' + s;
    vector <pair <int, int>> scol;
    for (int i = 1; i <= m; i ++)
    {
      int u, v;
      cin >> u >> v;
      u ++; v ++;
      if (s[u] != s[v])
        edge[u].push_back(v), 
        edge[v].push_back(u);
      else
        scol.push_back({u, v});
    }
    tarjan(1, 0);
    for (int i = 1; i <= n; i ++)
    {
      // cout << i << ": ";
      for (auto to : pt[i])
        cste[i].push_back(to + n), cste[to + n].push_back(i);//, cout << to << " ";
      // cout << endl;
    }
    init(1, 0, 1);
    int flag = 0;
    for (auto [u, v] : scol)
    {
      if (u == v)
        continue;
      if (!dfn[u] || !dfn[v])
        continue;
      // cout << u << " " << v << endl;
      if (u == 1 || v == 1)
      {
        flag = 1;
        break;
      }
      u = f[u][0], v = f[v][0];
      int lca = LCA(u, v);
      // cout << lca << endl;
      if (lca == v || lca == u)
      {
        flag = 1;
        break;
      }
    }
    cout << (flag ? "yes\n" : "no\n");
  }
  return 0;
}