设原串 $s$ 的每个前缀为 $s_1,s_2,...,s_n$，对应到 sam 上的节点编号是 $a_1,a_2,...,a_n$，你要求的就是 $\sum\limits_{i<j}len_{a_i}+len_{a_j}-len_{lca(a_i,a_j)}$。
你给每条边赋的权值是 $len_u-len_{fa_{u}}$，那么一条路径的边权和就是 $len_{a_i}+len_{a_j}-len_{lca(a_i,a_j)}$，也就是你要求的东西。所以说 $a_i$ 之间两两的路径长度之和就是答案。
接下来你就考虑一条边 $(u,fa_u)$ 对答案的贡献，显然是它的边权乘上经过它的路径条数，也就是 $sz_u \times (n-sz_u)\times (len_u-len_{fa_u})$。
by L_G_J @ 2022-07-03 16:46:46
@[sinsop90](/user/141599)
by L_G_J @ 2022-07-03 16:52:03
噢, thanks, 我以为把路径边权赋为1路径和就是那个东西了
@[L_G_J](/user/104413)
%%
by sinsop90 @ 2022-07-03 17:14:36