Christmas Game | Codeforces 1498F

发表于 分类于 本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目链接

给定一棵 \(n\) 个点的树和 \(k\)，每个结点上有 \(a_i\) 个物品，Alice 和 Bob 在上面玩游戏。

在确定根之后，两个玩家轮流选择任意一个存在 \(k\) 级祖先的结点 \(u\)，然后把 \(u\) 的任意个物品移到 \(u\) 的 \(k\) 级祖先上。

最后没有物品可取的人输。

问当每个结点作为根时，谁必胜。

\(n \le 10^5, k \le 20,a_i \le 10^9\)

当 \(k=1\) 时，它几乎是一个阶梯 NIM 游戏。

设根结点深度为 \(0\)，根据阶梯 NIM 游戏的结论，原问题等价于所有深度为奇数的结点做 NIM 游戏，即先手必胜当且仅当所有深度为奇数的结点的 \(a_i\) 异或和不为 \(0\)。

对于一般的情况，先手必胜当且仅当 \[ \bigoplus_{\big\lfloor \frac {depth_u}k \big\rfloor 为奇数}a_u \ne 0 \] 设 \(f_{u,i}\) 表示以 \(u\) 为根的子树里，所有满足 \(depth_v - depth_u \equiv i \pmod {2k}\) 的结点 \(v\) 的点权异或和。

然后换根 DP 一下即可。

复杂度 \(O(nk)\)。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)

using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, K, a[N];
ll f[N][40], ans[N];
vector <int> G[N];
void add(int u, int v) {
    For(i, 0, K) f[u][(i + 1) % K] ^= f[v][i];
}
void dfs(int u, int fa) {
    f[u][0] = a[u];
    for(int v : G[u]) if(v ^ fa) dfs(v, u), add(u, v);
}
void Dfs(int u, int fa) {
    For(i, K / 2, K) ans[u] ^= f[u][i];
    for(int v : G[u]) if(v ^ fa) add(u, v), add(v, u), Dfs(v, u), add(v, u), add(u, v);
}
int main() {
    cin >> n >> K, K *= 2;
    int u, v;
    rep(i, 2, n) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    rep(i, 1, n) scanf("%d", &a[i]);
    dfs(1, 0), Dfs(1, 0);
    rep(i, 1, n) printf("%d ", ans[i] != 0);
    return 0;
}