题目：https://www.luogu.com.cn/problem/CF700E

思路：

SAM上DP。

  1. 首先可以注意到我们可以限制DP的转移，使得短串向长串转移时必须是长串的后缀。（加限制）
  2. 然后可以注意到此时每个子串一定向SAM子树的子串转移，同时同一个节点的子串无法互相转移。
  3. 发现同一个节点的非最长串的转移（向他转移和他向别人转移）一定被包含在最长串的转移。
  4. 考虑每个节点最长串的转移子串（即谁向他转移的）一定可以是其祖先节点的最长串。
  5. 于是考虑限制只在每个节点最长串上转移，删掉了转移，答案只会非严格减少，同时由第四条可以知道，答案不会减少，综上，加上如上限制答案不变。
  6. 如果考虑从下往上DP，则需要倍增+线段树合并，两个log。
  7. 但是如果是从上到下更新，由于具有：能更新我父亲节点最长串的子串也一定能更新我自己的最长串的特点，每个节点要么等于父亲节点的dp值，要么+1，+1只需要判断父亲这条dp值相同的链的链头是否能转移到自己即可，行就+1，不行就不加，直接继承，这样子做是一个log的，只需要线段树合并。