给定一棵 4n−14n−14n−1 个节点的 二叉树，其中每个非叶节点都有 恰好 两个子节点。 非叶节点编号为 1∼2n−11∼2n−11∼2n−1，叶子节点编号为 2n∼4n−12n∼4n−12n∼4n−1。 初始时，每个叶子节点上都没有数字。 定义一个 DFSDFSDFS 序是优美的，当且仅当按该 DFSDFSDFS 序将所有 标有数字的叶子节点 上的数字拼成一个序列时，可以通过若干次 消除相邻相同数字 的方式删空。 给定 n 次操作，第 i 操作会选择两个 没有数字 的叶子节点ai ,bi a i ,b i ai ,bi ，然后将这两个节点标上数字 iii。 保证在每次操作后，存在至少一个优美的 DFSDFSDFS 序。 你需要求出每次操作后的优美的 DFSDFSDFS 序的数量，对 109+710^ 9 +7109+7 取模。 1≤n≤2×1051≤n≤2×10 51≤n≤2×105 部分分（特殊性质）：保证 ai ,bi a i ,b i ai ,bi 位于根节点 111 的不同子树中。 提示：观察发现大样例中所有答案中的数都形如 2k2 k2k ，其中 k≤2n−1k≤2n−1k≤2n−1。 下面结论来自国家集训队 rk.9hhoppitreerk.9 hhoppitreerk.9hhoppitree，太大神。 最开头给出结论： 定义一个点的权值为：子树内恰好出现过一次的数形成的集合。 设 Ci C i Ci 表示第 iii 次所有本质不同的权值个数。 则第 iii 次答案为 22n+i−Ci2 2n+i−C i 22n+i−Ci 。 如果懒得看证明可以直接跳到最后看如何维护。 不同 DFSDFSDFS 序能通过翻转 2n−12n−12n−1 个子树中的某些一一对应，下面考虑翻转子树。 根据提示，容易往某些方面想：比如找到一些相对独立的子树翻转的限制，那么答案就是 222 限制个数 。 经典套路：由于保证存在优美的 DFSDFSDFS 序，我们不妨设最开始的树的 DFSDFSDFS 序是满足条件的，然后去挖性质。 否则容易交换一些左右儿子调整成这样。 先考虑特殊性质。最终答案能删空的串一定形如：143223411432234114322341 这样。 子树等价于某个 DFSDFSDFS 序区间，拍平后性质更多，后面都用区间去叙述。 因为所有的点对都是经过根的，所以翻转了一段 DFSDFSDFS 序区间，就需要对应地翻转右边内容完全一样的区间！ 其中内容定义为区间恰好出现过一次的数形成的集合。 由于所有区间的内容形成了若干等价类，因此上述限制等价于：每个等价类必须恰好选择偶数个区间翻转。 简单点说等价类：就是相同权值的点在一个等价类内。 但是这东西有点小问题：翻转集合大小 ≤1≤1≤1 的区间没有意义，重写得严谨些： 上述限制等价于：每个内容里 >1>1>1 个元素的等价类必须恰好选择偶数个区间翻转。 我们发现大小为 000 的等价类共 111 个，第 iii 次会有 iii 个大小为 111 的等价类个数。 总共有 2n−12n−12n−1 个非叶子可以翻转。 于是设 Ci C i Ci 表示第 iii 次所有子树的形成的等价类个数。 由于每个必须恰好选择偶数个区间翻转的限制会使得方案数 /2/2/2，于是第 iii 次答案为： 22n−1−(Ci−i−1)=22n+i−Ci2 2n−1−(C i −i−1) =2 2n+i−C i22n−1−(Ci−i−1)=22n+i−Ci 如果没有特殊性质是否也一样呢？ 考虑根的两个子树，它们中有一些跨越根的和完全在内部的数字对。 对于任何一个点的子树，分析时只保留恰出现一次的数字，而忽略其它的。 如果只有跨过根的数字，和特殊性质的分析完全一致。 一个子树如果既包含跨越根的数字，又打乱了一些完全在内部的数字对，就一定要翻转偶数次。 这个结论可以反证：找到最上面的翻转了奇数次的子树，没有其它子树能救它，就一定不合法。 我们保留了只有完全在内部的数字对的情况，因此可以递归进根的两个子树各自分析。 于是我们证明了这个结论仍然成立！ 于是我们只需要求等价类个数：C1,C2,⋯,Cn。C 1 ,C 2 ,⋯,C n。 C1,C2,⋯,Cn。 本题后半部分和 qoj5425——PropositionCompositionqoj 5425——Proposition Compositionqoj5425——PropositionComposition 有点类似。 转换下参考对象，对每个数 i 刻画其在哪些子树出现过。 于是对 1∼4n−11∼4n−11∼4n−1 中的每个节点 i 记录字符串 sis isi ，其中 si,j =1s i,j =1si,j =1 表示 i 子树内 j 是否恰好出现一次 。 字符串数组 s 是容易线段树合并维护的，合并的时候做个 xorxorxor。 不难发现 xxx 和 yyy 位置等价的时刻是 [1,lcp(sx,xy )][1,lcp(s x ,x y )][1,lcp(sx,xy )] 这个区间 。 然后类似 SA 中 height 数组那类做法，我们排序所有 s，排序成 S 。 求出相邻两两的 d x =lcp(S x ,S x+1 )，容易发现第 i 次等价类个数就是 d x <i 的个数再 +1 ，随便前缀和一下。 为啥等价类个数是这个呢？大概就是排序后能表示所有大小相邻的不等价类，再 +1 就是等价类个数。 xor hash 维护等价类，排序和 lcp 直接线段树二分即可，记得开 unsigned long long。 时间复杂度 O(nlog 2 n)，空间 O(nlogn)。常数不要太大都足以通过。 官方题解说了个不一定跑得过 log 2 的单 log，讲一下。 注意到瓶颈在于最后的字典序排序，考虑优化。 发现只需将线段树合并中所有的 O(nlogn) 个节点排序即可！ 以每个节点的左右儿子的字典序为第 1,2 关键字，进行基数排序即可。 为了方便实现，把线段树长度补成 2 的次幂，从线段树的叶子（区间长度为 1）开始做，每次给一层排序。 时空复杂度均为 O(nlogn) ，足以通过。 其实感觉也没有特别难写，不过我不写 个人感觉有点像后缀平衡树，或者 P6272 没有人的算术？但是貌似没几个和我一样想的。 官方题解一个很唐的地方，是没有发现第 i 次恰好有 i 个大小为 1 的等价类。 我这样能直接算等价类个数，最后 −i 即可，比官方做法好写一万倍。 官方题解是真的算了大小 >1 的等价类个数，还要线段树多维护好多东西。 虽然归并排序 stable_sort 的比较次数 < 快速排序 sort 的比较次数，但是实际上 sort 跑得更快？有点神秘。 下面是 log 2 实现，代码非常非常短，跑挺快的： /