「洛谷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);
    }
  }
}