BZOJ_1777
说实话，下面的分析我也不知道究竟对不对，基本都是凭感觉来的，不过可以AC这个题。
首先这是个组合游戏，尝试从sg理论入手解决这个问题。感觉各个节点上的石子应该是相互独立的，这样我们只要依次计算出每个节点上有当期这些石子时sg值是多少，最后再将各个sg值异或起来就是整个局面的sg值。如果独立去计算每个节点的话，那么显然节点的位置是没有太大关系的，只和当前这个节点和根节点的距离有关。我们从离根结点最近的点开始依次向外递推，尝试去计算各个节点上有若干石头时的sg值，这时我们会发现，如果当前这个节点距离根节点的距离为奇数的话，那么这个节点石头数为0,1,2...时对应的sg值为0,1,2,...,L,0,1,2,...，如果当前这个节点距离根节点的距离为偶数的话，那么这个节点无论石头有多少个，sg值都是0。
#include<stdio.h> #include<string.h> #define MAXD 10010 #define MAXM 10010 int N, T, L, first[MAXD], e, next[MAXM], v[MAXM], a[MAXD], st[MAXD]; void add(int x, int y) { v[e] = y; next[e] = first[x], first[x] = e ++; } void dfs(int cur, int d) { st[cur] = d; for(int i = first[cur]; i != -1; i = next[i]) dfs(v[i], d ^ 1); } int getsg(int cur) { return st[cur] == 0 ? 0 : a[cur] % (L + 1); } void init() { memset(first, -1, sizeof(first)), e = 0; for(int i = 2; i <= N; i ++) { int p; scanf("%d%d", &p, &a[i]); add(p, i); } dfs(1, 0); } void solve() { int id, n, ans = 0; scanf("%d%d", &id, &n); a[id] = n; for(int i = 2; i <= N; i ++) ans ^= getsg(i); printf("%s\n", ans ? "Yes" : "No"); for(int i = 1; i < T; i ++) { scanf("%d%d", &id, &n); ans ^= getsg(id); a[id] = n; ans ^= getsg(id); printf("%s\n", ans ? "Yes" : "No"); } } int main() { while(scanf("%d%d%d", &N, &T, &L) == 3) { init(); solve(); } return 0; }