[ByteDance WC 2019 Online] Continued Story

发表于

2019 字节跳动冬令营网络赛 C 题。

题目大意

给定一棵 \(n\) 个节点的带权有根树，两人轮流操作，每次操作使某条边的边权减一，若边权减至 \(0\)，则删去改边，并删去不含根的连通块，判断先手是否必胜，并输出先手若要胜利，所有第一步可能的决策。

\(T\) 组数据。

\(1 \leq n \leq 10^6\)

\(1 \leq w_i \leq 10^9\)

\(\sum n \leq 10^6\)

题目链接

ByteDance WC 2019 Online - C

题解

现学的 Hackenbush 博弈。

计算 SG 函数：

\[ \begin{align} SG(u) &= f(v_1) \oplus f(v_2) \oplus \cdots \oplus f(v_m) \\ f(v) &= \begin{cases} SG(v) + 1 ~ &, w_{E(u, v)} = 1 \\ SG(v) ~ &, w_{E(u, v)} \text{ is even} \\ SG(v) \oplus 1 ~ &, w_{E(u, v)} > 1 \text{ and } w_{E(u, v)} \text{ is odd} \end{cases} \end{align} \]

如何输出方案：

我们从根节点开始 dfs，同时传递一个变量 \(need\)（代码中为 val）表示需要用该子树进行一次操作凑出的 SG 函数值，初始为 \(0\)。对于每一个点，枚举与它儿子相连的每一条边，可以分情况计算出该儿子对应子树的 \(need\) 的值（\(other\) 为其余部分的 SG 值，\(u, v\) 分别表示父节点、子节点）：

  • 边权为 \(1\)：\((need_v + 1) \oplus other = need_u\)
  • 边权大于 \(1\) 且为奇数：\(need_v \oplus 1 \oplus other = need_u\)
  • 边权为偶数：\(need_v \oplus other = need_u\)

同时，可以考虑若操作该边是否能得到该点的 \(need\) 值：

  • 边权为 \(1\)：\(other = need_u\) 则可以
  • 边权为 \(2\)：\((SG(v) + 1) \oplus other = need_u\) 则可以
  • 边权大于 \(2\)：\(SG(v) \oplus 1 = need_u\) 则可以

代码

吐槽1：比赛时没有给异或运算加括号，于是输给了运算符优先级。。。QAQ

吐槽2：代码中的 MAXN = 1000105 原本是 MAXN = 1000005，但发生了迷之「内部错误」。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <vector>
#include <algorithm>
 
const int MAXN = 1000105;
 
struct Edge;
 
struct Node {
    Edge *e;
    int sg;
} N[MAXN];
 
struct Edge {
    Node *u, *v;
    Edge *next;
    int w;
 
    Edge() {}
    Edge(Node *u, Node *v, int w) : u(u), v(v), w(w), next(u->e) {}
} _pool[MAXN], *_curr;
 
void addEdge(int f, int s, int w) {
    N[f].e = new (_curr++) Edge(&N[f], &N[s], w);
}
 
void dfs(Node *u) {
    u->sg = 0;
    for (Edge *e = u->e; e; e = e->next) {
        dfs(e->v);
 
        if (e->w == 1) u->sg ^= (e->v->sg + 1);
        else if (e->w % 2 == 0) u->sg ^= e->v->sg;
        else u->sg ^= (e->v->sg ^ 1);
    }
}
 
std::vector<int> ans;
void dfs(Node *u, int val) {
    if (val < 0) return;
    for (Edge *e = u->e; e; e = e->next) {
        int other;
        if (e->w == 1) other = u->sg ^ (e->v->sg + 1);
        else if (e->w % 2 == 0) other = u->sg ^ e->v->sg;
        else other = u->sg ^ e->v->sg ^ 1;
 
        if (other == val && e->w == 1) ans.push_back(e->v - N);
        else if (((e->v->sg + 1) ^ other) == val && e->w == 2) ans.push_back(e->v - N);
        else if (val == (u->sg ^ 1) && e->w > 2) ans.push_back(e->v - N);
        
        if (e->w == 1) dfs(e->v, (val ^ other) - 1);
        else if (e->w % 2 == 0) dfs(e->v, val ^ other);
        else dfs(e->v, val ^ other ^ 1);
    }
}
 
void init(int n) {
    _curr = _pool;
    for (int i = 1; i <= n; i++) N[i].e = NULL;
}
 
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        init(n);
 
        for (int i = 2, f, w; i <= n; i++) {
            scanf("%d %d", &f, &w);
            addEdge(f, i, w);
        }
 
        dfs(&N[1]);
        ans.clear();
        dfs(&N[1], 0);
        
        std::sort(ans.begin(), ans.end());
        printf("%d\n", ans.size());
        for (int i : ans) printf("%d ", i);
        puts("");
    }
     
    return 0;
}