虽然vfleaking好像想卡DFS...但我还是用DFS过了...
路径上的石堆异或和=0就是必败, 否则就是必胜(nim游戏).
这样就变成一个经典问题了, 用DFS序+BIT+LCA就可以在O((N+Q)logN)时间内AC
---------------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
#define lowbit(x) ((x) & -(x))
const int maxn = 500009;
inline int read() {
char c = getchar();
int ret = 0;
for(; !isdigit(c); c = getchar());
for(; isdigit(c); c = getchar())
ret = ret * 10 + c - '0';
return ret;
}
struct edge {
int to;
edge* next;
} E[maxn << 1], *pt = E, *head[maxn];
inline void AddEdge(int u, int v) {
pt->to = v;
pt->next = head[u];
head[u] = pt++;
}
int N, w[maxn], seq[maxn], n, L[maxn], R[maxn];
int fa[maxn], son[maxn], top[maxn], sz[maxn], dep[maxn], Top;
void DFS0(int x) {
sz[x] = 1;
son[x] = -1;
for(edge* e = head[x]; e; e = e->next) if(e->to != fa[x]) {
fa[e->to] = x;
dep[e->to] = dep[x] + 1;
DFS0(e->to);
sz[x] += sz[e->to];
if(son[x] == -1 || sz[e->to] > sz[son[x]])
son[x] = e->to;
}
}
void DFS1(int x) {
top[x] = Top;
if(son[x] != -1)
DFS1(son[x]);
for(edge* e = head[x]; e; e = e->next)
if(e->to != fa[x] && e->to != son[x]) DFS1(Top = e->to);
}
int Lca(int x, int y) {
for(; top[x] != top[y]; x = fa[top[x]])
if(dep[top[x]] < dep[top[y]]) swap(x, y);
return dep[x] < dep[y] ? x : y;
}
void DFS2(int x) {
seq[L[x] = ++n] = x;
for(edge* e = head[x]; e; e = e->next)
if(e->to != fa[x]) DFS2(e->to);
R[x] = n;
}
struct BIT {
int b[maxn];
BIT() {
memset(b, 0, sizeof b);
}
inline void Modify(int x, int v) {
for(; x <= N; x += lowbit(x))
b[x] ^= v;
}
inline int Sum(int x) {
int ret = 0;
for(; x; x -= lowbit(x))
ret ^= b[x];
return ret;
}
inline int Query(int l, int r) {
return Sum(r) ^ Sum(l - 1);
}
} Bit;
void Init() {
N = read();
for(int i = 0; i < N; i++)
w[i] = read();
for(int i = 1; i < N; i++) {
int u = read() - 1, v = read() - 1;
AddEdge(u, v);
AddEdge(v, u);
}
}
void Work() {
dep[0] = 0;
fa[0] = -1;
DFS0(0);
DFS1(Top = 0);
DFS2(n = 0);
for(int i = 0; i < N; i++) {
Bit.Modify(L[i], w[i]);
Bit.Modify(R[i] + 1, w[i]);
}
int Q = read();
char c;
while(Q--) {
scanf(" %c", &c);
if(c == 'Q') {
int x = read() - 1, y = read() - 1;
int res = Bit.Query(1, L[x]) ^ Bit.Query(1, L[y]);
puts(res != w[Lca(x, y)] ? "Yes" : "No");
} else {
int p = read() - 1;
Bit.Modify(L[p], w[p]);
Bit.Modify(R[p] + 1, w[p]);
Bit.Modify(L[p], w[p] = read());
Bit.Modify(R[p] + 1, w[p]);
}
}
}
int main() {
Init();
Work();
return 0;
}
---------------------------------------------------------------------------------
2819: Nim
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 1551 Solved: 578
[Submit][Status][Discuss]
Description
著名游戏设计师vfleaking，最近迷上了Nim。普通的Nim游戏为：两个人进行游戏，N堆石子，每回合可以取其中某一堆的任意多个，可以取完，但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是vfleaking决定写一个玩Nim游戏的平台来坑玩家。
为了设计漂亮一点的初始局面，vfleaking用以下方式来找灵感：拿出很多石子，把它们聚成一堆一堆的，对每一堆编号1,2,3,4,...n,在堆与堆间连边，没有自环与重边，从任意堆到任意堆都只有唯一一条路径可到达。然后他不停地进行如下操作：
1.随机选两个堆v,u，询问若在v到u间的路径上的石子堆中玩Nim游戏，是否有必胜策略，如果有，vfleaking将会考虑将这些石子堆作为初始局面之一，用来坑玩家。
2.把堆v中的石子数变为k。
由于vfleaking太懒了，他懒得自己动手了。请写个程序帮帮他吧。
Input
第一行一个数n，表示有多少堆石子。
接下来的一行，第i个数表示第i堆里有多少石子。
接下来n-1行，每行两个数v,u，代表v,u间有一条边直接相连。
接下来一个数q，代表操作的个数。
接下来q行，每行开始有一个字符：
如果是Q，那么后面有两个数v,u，询问若在v到u间的路径上的石子堆中玩Nim游戏，是否有必胜策略。
如果是C，那么后面有两个数v,k，代表把堆v中的石子数变为k。
对于100%的数据：
1≤N≤500000, 1≤Q≤500000, 0≤任何时候每堆石子的个数≤32767
其中有30%的数据：
石子堆组成了一条链，这3个点会导致你DFS时爆栈（也许你不用DFS？）。其它的数据DFS目测不会爆。
注意：石子数的范围是0到INT_MAX
Output
对于每个Q，输出一行Yes或No，代表对询问的回答。
Sample Input
【样例输入】
5
1 3 5 2 5
1 5
3 5
2 5
1 4
6
Q 1 2
Q 3 5
C 3 7
Q 1 2
Q 2 4
Q 5 3
Sample Output
Yes
No
Yes
Yes
Yes
HINT
Source
