模拟30A 题解
A. 树
B. 回文串
C. 异或
A. 树
联想起远古考试时做的题 记忆的轮廓。
树上走一些步数的期望。
显然可以直接解方程。
然而复杂度$O(qn^3)$，利用树上的性质优化一下，
直接一遍dfs过程中解出来，可以$O(qnlogmod)$，其中的log是求逆元。
然而只有20分。
预处理出每个点走到每个儿子的期望步数，走到父亲的期望步数。
树上倍增求lca，处理两个函数的树上前缀和就完了。
B. 回文串
串A的后缀与串B的前缀构成回文串，
一定满足：
A的后缀与B的前缀翻转后匹配，
A的后缀之前 或者 B的前缀之后 存在一段回文串。
加上字符串哈希。
可以预处理出由每个点开始的回文串。
预处理$O(n^2)$，询问$O(qn)$。
转变预处理思路。
枚举回文串的起始点，复杂度无法接受。
转化为枚举回文串的中间点，二分加哈希判断，差分进行区间修改。
预处理复杂度为$O(nlogn)$。
对于每个询问，也可以二分匹配长度，用前缀和直接统计答案。
询问$O(qlogn)$。
考场上得到了$O(n^2+qn)$的做法，但局限于枚举起始点。
拓展一下思路，也许就能打出正解。
C. 异或
考场上的暴力：枚举起始点，直接dfs。
复杂度$O(n^2)$，44分。
正解一：题中给出的条件，一定满足0～k-1内的数，在定义的运算下，是一个群。
也就是说存在单位元和逆元。
求出dfs序，以dfs序为下标建线段树，维护每个节点每个值的方案数。
使用树上启发式合并的思路，直接继承重儿子，暴力dfs轻儿子并统计答案。
因为一定搜索出一条链，对于ban掉的情况，直接打标记，在回溯时清掉标记。
复杂度显然为$O(nklog^2n)$。
似乎可以优化到$O(nklogn)$，不会。
版权声明：本文为skyh原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。