【学习笔记】「北大集训 2021」经典游戏

我觉得很厉害。要是考场上能把这道题切了的话数据结构的水平肯定是不低的。

考虑简化版问题：如果只询问一个点的答案怎么做。

注意，我这么做是有风险的。我把战线拉长了。不过当然，如果连简化版的问题都做不了，那何谈正解？幸运的是，这确实是一道数据结构多合一的题。

考虑 长链剖分 。那么在$x$节点上加入棋子时，子树外的点就异或上$x$子树的最大深度，如果以$x$为根的最长链在重儿子上面，那么就给除了重儿子外的子树打标记，注意到 其$\text{dfn}$序是连续的 ，可以直接打标；对于重儿子也可以直接对整颗树打标，只需处理出$x$去掉重儿子后的最长链长度即可；如果最长链在父亲上，那么直接对$x$整颗子树修改即可。

发现了吗？经过细致分析，我们发现这道题其实并不复杂。当然要建立在想到长链剖分的基础上。

这题更神奇的地方在于，让我们求$\text{dist(x,v)}\le 1$的所有根的答案。这是个非常恼人的限制，因为你知道会被菊花图卡，但是不知道会被卡成多少分。

有没有严格的做法呢？答案是有的。但是我一定想不到。 但是需要用到非常高级的技巧。其实说白了，询问可以拆分成$x$，$x$的父亲，$x$的重儿子以及$x$的所有轻儿子。如果一次插入影响到点的数目是$O(1)$那么我们的目的就达到了。

考虑这样一个问题，如何用字典树维护$c_i\oplus x>d_i$的所有点对？这个问题也非常具有迷惑性。因为$d_i$是定值，$x$又是每次询问给定的，那么维护$c_i$然后在$\text{trie}$树上查不就完了？并且$\text{trie}$树查询的复杂度也是$\log n$的。这样分析下来觉得越来越有道理了，但是考场上完全想不到这里来啊？？？

初始化的时候$c_i$都是定值。手动分讨一波，如果最长链在重儿子上面那么$x$的所有轻儿子都异或上同一个数，直接在$x$上打标就完了；如果最长链在父亲上面那么轻儿子还是异或上同一个数。事实上可以发现，任意时刻轻儿子的标都和这个点上的标是一样的，唯一的例外是当插入的点就是这个轻儿子的情况。但是正如前所说，修改影响到的节点数目是$O(1)$的，所以直接在$\text{trie}$树上暴力修改就行。然后就做完了。

所以发现了吗？这种题逻辑链条太长了。其实思维难度并不大。

复杂度$O(n\log n)$。

要考虑的细节挺多了。所以代码先咕了。