【日常小测】相似子串

题目大意

给定一棵$n(n \le 10^5)$的无根树，每条边上有一个字符
定义$str_{u,v}$为从$u$走到$v$,将边上的字符按顺序写下来得到的字符串
给定$m(m \le 10^5)$个询问，每一次询问会定义$k_i$种形如$a,b$这样的等价关系，意义为将所有的$a,b$字符视为同一个字符（关系具有传递性）
对于每一个询问还会给定$u_1,v_1,u_2,v_2$四个点，请你回答$str_{u_1,v_1}$与$str_{u_2,v_2}$是否至多有一个位置不匹配

解题报告

这种奇怪的匹配题目除了$FFT$之外，似乎只能$Hash$了吧？

我们先来考虑没有等价类，且是一条链的情况

定义$Hash$函数$f_{i,u,v}$为对于第$i$种字符来讲，$str_{u,v}$的$Hash$值
更进一步，$f_{i,u,v}=\sum\limits_{j=u}^{v}{[char_j=i] \cdot G^{j-u+1}}$
那么这两个字符串的$Hash$值只能在两种字符下不同，且这两种字符差的$G$的次幂相等

考虑快速求得$Hash$值，这个很简单，做一个前缀和就好
考虑快速求的差值对应的$G$的次幂，这个我们先预处理一下，然后扔到一个$map$里去就可以了
至此我们已经能在$O(|\sum|+\log n)$的时间复杂度内回答单个询问了

现在考虑加入等价类，这个我们可以将整个等价类的$Hash$值加起来一起比较就可以了
至于不是链的情况，那我们求个到根前缀和就能够解决问题啦！
至此我们已经在$O(n \log n + m (|\sum| + \log n))$的时间复杂度内解决了这个问题