rt，我在 parent 树上跑 DP 。

f[i] 表示点 i 为结尾的字串出现了几次。

下面这种写法会 WA ：

void dfs(const int x){
  f[x]=1;
  //...枚举出边，然后 DP
}

而改成这样就对了：

void SAM_extend(int c){
  int cur=++siz;
  f[siz]=1;
  //...构造 SAM
}
void dfs(const int x){
  //f[x]=1;
  //...枚举出边，然后 DP
}

完整代码：Link