AT_joisc2016_g ダンジョン2

不妨先建出一棵 dfs 树，然后给每个点标号。那么现在就是要确定所有非树边的端点。

考虑三进制拆分，第 \(i\) 轮每个点颜色为其第 \(i\) 位的值。

于是可以求出每条非树边终点的第 \(i\) 位。这样只要跑 \(\log_3n\le5\) 次。

不妨把每条非树边挂到较低点求值，实现可以考虑定义颜色 \(3\) 为已回溯，\(2\) 为访问且未回溯，\(1\) 为未访问。每次判断两端颜色都为 \(2\) 即可。

于是这样 Move 次数为 \(4m+5\times 2\times m=14m\) 次，可以通过。

#include "dungeon2.h"
#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;

const int kN = 205;
const vector<int> pw3 {1, 3, 9, 27, 81};
int n;
array<int, kN> ans, deg;
array<bool, kN> vis;
array<array<int, kN>, kN> dis;
array<vector<int>, kN> to, val;

void build(int x, int fa) {
  int fa_edge = LastRoad();
  deg[x] = NumberOfRoads();
  to[x] = val[x] = vector<int> (deg[x] + 1, 0);
  if(x != 1) to[x][fa_edge] = -fa;
  for(int i = 1; i <= deg[x]; i++) {
    if(i == fa_edge) continue;
    Move(i, 2);
    if(Color() == 1) {
      n++, to[x][i] = -n;
      dis[x][n] = dis[n][x] = 1;
      build(n, x);
    }else {
      if(Color() == 3) {
        to[x][i] = -kN;
      }
      Move(LastRoad(), 2);
    }
  }
  if(x != 1) Move(fa_edge, 3);
}

void find(int x, int w) {
  int fa_edge = LastRoad();
  if(x == 1) fa_edge = -1;
  int col = x / pw3[w] % 3 + 1;
  for(int i = 1; i <= deg[x]; i++) {
    if(i == fa_edge) continue;
    if((to[x][i] < 0) && (to[x][i] != -kN)) {
      Move(i, col);
      find(-to[x][i], w);
    }
  }
  for(int i = 1; i <= deg[x]; i++) {
    if((to[x][i] >= 0) && (val[x][i] == -1)) {
      Move(i, col);
      val[x][i] = Color() - 1;
      Move(LastRoad(), Color());
    }
  }
  if(x != 1) Move(fa_edge, col);
}

void Inspect(int R) {
  const int kInf = 1e9;
  for(auto& k : dis) k.fill(kInf);
  for(int i = 0; i < kN; i++) {
    dis[i][i] = 0;
  }

  build(n = 1, 0);
  for(int i = 0; i < 5; i++) {
    for(int j = 1; j <= n; j++) {
      fill(ALL(val[j]), -1);
    }
    find(1, i);
    for(int j = 1; j <= n; j++) {
      for(int k = 1; k <= deg[j]; k++) {
        if(to[j][k] >= 0) {
          to[j][k] += pw3[i] * val[j][k];
        }
      }
    }
  }
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= deg[i]; j++) {
      if(to[i][j] >= 0) {
        int id = to[i][j];
        dis[i][id] = dis[id][i] = 1;
      }
    }
  }

  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
      for(int k = 1; k <= n; k++) {
        dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
      }
    }
  }
  for(int i = 1; i <= n; i++) {
    for(int j = i + 1; j <= n; j++) {
      ans[dis[i][j]]++;
    }
  }
  for(int i = 1; i <= R; i++) {
    Answer(i, ans[i]);
  }
}