题目描述
给定一棵树，每个节点有一个权值 (a_i) 和一个字符串 (s_i)。
q组询问，每次询问一个字符串 S 和两个节点x,y：
求x到y路径上每个节点的字符串在 S 中出现的次数乘上各自的权值总和。
有单点修改权值的操作。
$n,qleq 200000,sum s_i,sum Sleq 400000 $
强制在线，但询问串不加密。
sol
先 Orz 神仙Jouna_Kasa_Hasinele
首先考虑一下平方级别的做法，每次询问的时候建一个后缀自动机，遍历所有节点，统计作为 (s_i) 且出现在 <u,v> 路径上的串乘上 (a_i) 之和。
把这个做法弄的好一点，预处理所有询问串的广义后缀自动机，并把所有 (s_i) 以及对应的信息挂在该子串节点上。
对于做某个询问串时，只考虑与该串相关的节点，统计 (sum size_i imes a_i = sum (size_i imes sum a_j))。
前一个求和号，由于建后缀树的总点数复杂度是对的可以直接枚举，算 size 直接用树状数组可以维护。
后一个求和号必须要动态维护：
因为有位于 <u,v> 路径上的限制，就树上差分+欧拉序列维护一下，可以转换为欧拉序上的 4 段前缀和。
对每个后缀自动机节点维护平衡树/动态开点线段树，支持修改 (a_i) 以及查前缀和即可。
时间复杂度 (O((q+|S|)log n))。