题面
首先学过博弈论的一眼就看出来要求链上权值的SG函数值异或和为0
于是考虑搞出SG函数值，然后点分治乱搞
打表得
$k=1:SG(i)=i$
$k=2:$
当s为奇数，$SG(x)=x \mod 2$
否则有一个$s + 1$的循环节$0,1,0,1,0,1\cdots0,1,2$
$k=3:$
$SG(x)=\lfloor\frac{x}{s}\rfloor$
$k=4:$
$SG(x)=sg(x)=
\begin{cases}
0, x=0\\
x, x\equiv 1,2 \mod4 \\
x+1,x\equiv 3 \mod4 \\
x-1,x\equiv 0 \mod4
\end{cases}$
这个打表伪代码放一下1
2
3
4
5
6
7
8
9SG(0) = 0
SG(1) = 1
for i from 2 to n:
set s
for j from 1 to n - 1:
s |= {SG(j)}
for j from i to n - 1:
s |= {SG(j) xor SG(i - j)};
SG(i) = mex(s)
注意一下几个游戏的和的SG函数值就是异或和
然后点分即可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
87
88
89
90
91
92
93
using namespace std;
int w[30010], head[30010], tot;
int k, n, s;
int rt, sum, sze[30010], vis[30010], wsze[30010];
unordered_set<int> Set;
int ans;
struct edge {
int v, nxt;
} e[60010];
inline void addedge(int u, int v) {
e[++tot] = edge{v, head[u]};
head[u] = tot;
}
inline void get_size(int now, int f) {
sze[now] = 1;
wsze[now] = 0;
for(int i = head[now]; i; i = e[i].nxt) {
if(vis[e[i].v] || e[i].v == f) continue;
get_size(e[i].v, now);
sze[now] += sze[e[i].v];
wsze[now] = max(wsze[now], sze[e[i].v]);
}
wsze[now] = max(wsze[now], sum - sze[now]);
if(rt == 0 || wsze[now] < wsze[rt]) rt = now;
}
inline void dfs1(int now, int f, int noww) {
noww ^= w[now];
Set.insert(noww);
for(int i = head[now]; i; i = e[i].nxt) {
if(e[i].v == f || vis[e[i].v]) continue;
dfs1(e[i].v, now, noww);
}
}
inline void dfs2(int now, int f, int noww) {
noww ^= w[now];
if(Set.count(noww)) return ans = 1, void();
for(int i = head[now]; i; i = e[i].nxt) {
if(e[i].v == f || vis[e[i].v]) continue;
dfs2(e[i].v, now, noww);
if(ans == 1) return;
}
}
int tmp[30010], cnt;
inline void solve(int now) {
rt = 0;
get_size(now, 0);
get_size(now = rt, 0);
vis[now] = 1;
cnt = 0;
for(int i = head[now]; i; i = e[i].nxt) if(vis[e[i].v] == 0) tmp[cnt++] = e[i].v;
Set.clear();
Set.insert(w[now]);
for(int i = 0; i < cnt; i++) {
dfs2(tmp[i], now, 0);
dfs1(tmp[i], now, w[now]);
if(ans == 1) return;
}
if(ans == 1) return;
for(int i = head[now]; i; i = e[i].nxt) {
if(vis[e[i].v]) continue;
sum = sze[e[i].v];
solve(e[i].v);
if(ans == 1) return;
}
}
int _f[] = {-1, 0, 0, 1};
int main() {
int t;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
sum = n;
memset(vis, 0, sizeof vis);
memset(head, 0, sizeof head);
tot = ans = 0;
for(int i = 1, u, v; i < n; i++) scanf("%d%d", &u, &v), addedge(u, v), addedge(v, u);
for(int i = 1; i <= n; i++) scanf("%d", w + i);
scanf("%d", &k);
if(k == 2 || k == 3) scanf("%d", &s);
for(int i = 1; i <= n; i++) {
if(k == 1) w[i] = w[i];
else if(k == 2) w[i] = s % 2 ? w[i] % 2 : w[i] % (s + 1) == s ? 2 : w[i] % (s + 1) % 2;
else if(k == 3) w[i] /= s;
else w[i] = w[i] == 0 ? 0 : w[i] + _f[w[i] % 4];
if(w[i] == 0) ans = 1;
}
solve(1);
if(ans) puts("Mutalisk ride face how to lose?");
else puts("The commentary cannot go on!");
}
return 0;
}