LINK:树论
不愧是我认识的出题人 出的题就是牛掰 == 他好像不认识我
考试的时候 只会写42 还有两个subtask写挂了 拿了37 确实两个subtask合起来只有5分的好成绩
父亲能转移到自己的子树内部的一点所以要从叶子结点往根考虑.
一个棋子的时候 单独某个点的SG函数不难推 这个点可以放到儿子任意一点 而儿子的SG函数值已知就很容易推出来了.
当然叶子结点的SG函数值为0.
显然整棵树的SG函数为异或和 可以看成若干个不交的游戏的组合.
考虑某个点两个棋子的时候的SG函数 经过不断的推导/猜想可以发现为0因为这两个棋子互不干扰 也可以看成是两个游戏的组合 所以可以直接异或起来.
进一步的可以推得 某个点的SG函数 如果为偶数那么为0 如果为奇数就是自己子树内部离自己最远的儿子的距离.
这样就可以写出一个\(n\cdot m\)的暴力了。
考虑每次根都为1的情况 显然每次只有子树内部加 链加的操作。
直接树链剖分 翻转一下标记即可.
考虑只存在操作1 且每次为单点修改操作.
经过观察可以发现某个点SG函数只有两种 利用线段树维护dfs序的以每个点为根的值.
容易在线段树上完成修改 要么是连续的一段 要么是两头.
这样每次单点修改就再次异或一下即可.
考虑只存在操作1的情况.
比上个情况其实多了一个链加 和 子树的修改.
都不太好做其实.
考虑正解。考虑直径的中点.
每个点的两种值 在以直径中点为根的时候变化比较规律.
如 当直径中点的时候 每个点都为自己子树内部的最大深度.
换根的时候 其实是 只有根到换到的那个点路径上的点会变化
这样就解决了换根的问题 在线段树上直接交换即可。
考虑链加 也可以直接做了.
子树加 考虑和当前根的关系 如果是子树外面那部分的可以考虑求出x到根的第一个点翻转再整体翻转即可。
线段树内部的话要维护四个值。
每次行翻转或者列翻转打上标记即可.