「洛谷P3727」曼哈顿计划E 题解

题目

分析

发现实质上是把树上一段链拉下来玩 Nim 游戏,若链上 $sg$ 函数的异或和为 $0$ 则先手必败,于是可以考虑点分治找出树上异或和为 $0$ 的链,用自己喜欢的 Hash 方式即可

SG 函数

  1. $k=1$:原始的 Nim 游戏 $sg(x)=x$
  2. $k=2$:分两种情况,(1) $s$ 为奇数,显然 $s^k$ 均为奇数,故简单归纳可得 $sg(x)=x\bmod 2$;(2) $s$ 为偶数,找规律得有长为 $(s+1)$ 的循环节,大概长这样 $\overbrace{0101\cdots01}^{s}2$,有 $1=(s+1)\times0+1,s=(s+1)\times1-1,s^2=(s+1)\times(s-1)+1,s^3=(s+1)\times(s^2-s+1)-1\cdots$ 于是对循环节施加归纳,每个点可看做前后两个点的 $\operatorname{mex}$ 即可得证
  3. $k=3$:$sg(x)=\lfloor\frac{x}{s}\rfloor$ 证明大概是对循环节施加归纳,每个循环节可以到达所有之前的循环节,即可得证
  4. $k=4$:$sg(x)=\begin{cases}0&(x=0)\\x&(x\equiv1,2\pmod4)\\x+1&(x\equiv3\pmod4)\\x-1&(x\equiv4\pmod4)\end{cases}$ 证明大概是先 $4$ 个分一块并对块施加归纳,再对每一种单独证明
    首先对于一个完整的块 $x=4k+1\sim 4k+4$ 它的 $sg(x)$ 取遍了 $4k+1\sim4k+4$,所以直接取的 $sg$ 值可以取遍 $0\sim 4k$
    以下 $1,2,3,4$ 均为 $\bmod 4$ 意义下的
    考虑 $1$ 分成 $1+0$ 时异或值为 $1\oplus3=2\neq1$,$2+3$ 时异或值为 $2\oplus0=2\neq1$ 故无法将 $1$ 分解得到自身,又因为能直接取到 $0\sim4k$ 故 $sg(4k+1)=4k+1$
    $2$ 也无法分解,证明是类似的,又因为能直接取到 $0\sim4k+1$ 故 $sg(4k+2)=4k+2$
    $3$ 可以直接取到 $0\sim4k+2$,又可以分解为 $4k+2$ 和 $1$,即 $(4k+2)\oplus1=4k+3$,故 $sg(4k+3)=4k+4$
    $4$ 可以直接取到 $0\sim4k+2$ 和 $4k+4$,类似 $1,2$ 的情况 $4$ 无法分解为 $4k+3$ 故 $sg(4k+4)=4k+3$

代码

constexpr int N = 30005;
constexpr int M = 60005;

void add(int u, int v);
void getsiz(int u, int fa);
void getrot(int u, int fa);
void getp(int u, int fa, int len);
void solve(int u);
void dfs(int u);

int hed[N], nxt[M], to[M], id;
int siz[N];
int asz, nsz, rot;
int dis[N], tot;
bool vis[N];
int val[N], sg[N];
bool ans;
int n;

int main() {
  int T;
  read(T);
  while (T--) {
    memset(hed, 0, sizeof(hed));
    id = 0;
    ans = false;
    memset(vis, false, sizeof(vis));
    read(n);
    for (int i = 1; i < n; ++i) {
      int u, v;
      read(u), read(v);
      add(u, v), add(v, u);
    }
    for (int i = 1; i <= n; ++i) {
      read(val[i]);
    }
    int k;
    read(k);
    if (k == 1) {
      for (int i = 1; i <= n; ++i) {
        sg[i] = val[i];
      }
    }
    if (k == 2) {
      int s;
      read(s);
      for (int i = 1; i <= n; ++i) {
        if (val[i] % (s + 1) == s) {
          sg[i] = 2;
        } else {
          sg[i] = val[i] % (s + 1) % 2;
        }
      }
    }
    if (k == 3) {
      int s;
      read(s);
      for (int i = 1; i <= n; ++i) {
        sg[i] = val[i] / s;
      }
    }
    if (k == 4) {
      for (int i = 1; i <= n; ++i) {
        if (!val[i]) {
          sg[i] = 0;
        } else {
          if (val[i] % 4 == 0) {
            sg[i] = val[i] - 1;
          } else {
            if (val[i] % 4 == 3) {
              sg[i] = val[i] + 1;
            } else {
              sg[i] = val[i];
            }
          }
        }
      }
    }
    getsiz(1, 0);
    asz = siz[1];
    nsz = iinf;
    rot = 0;
    getrot(1, 0);
    dfs(rot);
    if (ans) {
      puts("Mutalisk ride face how to lose?");
    } else {
      puts("The commentary cannot go on!");
    }
  }
  return 0;
}

void add(int u, int v) {
  nxt[++id] = hed[u];
  hed[u] = id;
  to[id] = v;
}
void getsiz(int u, int fa) {
  siz[u] = 1;
  for (int i = hed[u]; i; i = nxt[i]) {
    int v = to[i];
    if (v != fa && !vis[v]) {
      getsiz(v, u);
      siz[u] += siz[v];
    }
  }
}
void getrot(int u, int fa) {
  int maxi = 0;
  for (int i = hed[u]; i; i = nxt[i]) {
    int v = to[i];
    if (v != fa && !vis[v]) {
      getrot(v, u);
      maxi = max(maxi, siz[v]);
    }
  }
  maxi = max(maxi, asz - siz[u]);
  if (maxi < nsz) {
    nsz = maxi;
    rot = u;
  }
}
void getp(int u, int fa, int len) {
  len ^= sg[u];
  dis[++tot] = len;
  for (int i = hed[u]; i; i = nxt[i]) {
    int v = to[i];
    if (v != fa && !vis[v]) {
      getp(v, u, len);
    }
  }
}
void solve(int u) {
  if (!sg[u]) {
    ans = true;
  }
  if (ans) {
    return;
  }
  std::unordered_set<int> S;
  S.insert(sg[u]);
  for (int i = hed[u]; i; i = nxt[i]) {
    int v = to[i];
    if (!vis[v]) {
      tot = 0;
      getp(v, u, 0);
      for (int j = 1; j <= tot; ++j) {
        if (S.count(dis[j])) {
          ans = true;
          return;
        }
      }
      for (int j = 1; j <= tot; ++j) {
        S.insert(dis[j] ^ sg[u]);
      }
    }
  }
}
void dfs(int u) {
  vis[u] = true;
  solve(u);
  for (int i = hed[u]; i; i = nxt[i]) {
    int v = to[i];
    if (!vis[v]) {
      getsiz(v, u);
      asz = siz[v];
      nsz = iinf;
      rot = 0;
      getrot(v, u);
      dfs(rot);
    }
  }
}

本博客采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可
本文链接:https://blog.seniorious.cc/2020/luogu-3727/