题干信息解读

每头奶牛的名字是由小写字母组成的字符串，所有名字的总长度不超过 $10^{5}$ 。对于每头奶牛，其 "独特性因子" 定义为仅出现在该奶牛名字中，而不出现在其他任何奶牛名字中的所有不同子串的数量。需要计算并输出每头奶牛的独特性因子。

整体做题思路

1.构建广义后缀自动机：将所有奶牛的名字合并构建一个广义后缀自动机，每个节点记录其所属的名字编号。
2.树形 DP 处理父链关系：通过 DFS 遍历后缀自动机的 fail 树，处理每个节点的父链关系，标记出只属于一个名字的节点。
3.计算独特性因子：遍历所有节点，累加那些仅属于一个名字的节点的贡献（即该节点的子串数量）。

难点和注意事项

1.广义后缀自动机的构建：需要正确处理多个字符串合并时的状态转移和克隆操作。
2.父链关系处理：在 DFS 过程中需要正确判断节点是否只属于一个名字，并处理父链传递的影响。
3.时间与空间优化：处理大规模输入时需注意内存使用和算法效率，避免 TLE 或 MLE。

AC代码（如有雷同，纯属巧合）（改编自@捏总讨厌WA）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
typedef int LL;
const LL maxn=200009;
LL n,m,nod=1,lst;                // nod表示后缀自动机的节点数，lst表示当前活动节点
LL len[maxn],fail[maxn],son[maxn][26],visit[maxn],ans[maxn],mark[maxn];
// len[i]表示节点i对应的最长子串长度，fail[i]表示后缀链接，son[i][c]表示转移边
// visit[i]标记节点是否被访问，ans[i]存储最终答案，mark[i]标记节点所属的名字编号
string s;

// 插入字符构建后缀自动机
inline void Insert(LL c,LL id){
    LL np=++nod,p=lst; lst=np; mark[np]=id;  // 创建新节点并标记所属名字
    len[np]=len[p]+1;
    while(p&&!son[p][c]){  // 沿fail链向上查找没有c转移的节点
        son[p][c]=np;
        p=fail[p];
    }
    if(!p)
        fail[np]=1;  // 若找到根节点
    else{
        LL q=son[p][c];
        if(len[q]==len[p]+1)
            fail[np]=q;  // 情况1：直接链接
        else{
            LL nq=++nod; len[nq]=len[p]+1; mark[nq]=mark[q];  // 克隆节点
            memcpy(son[nq],son[q],sizeof(son[q]));
            fail[nq]=fail[q];
            fail[np]=fail[q]=nq;
            while(p&&son[p][c]==q){  // 更新所有指向q的转移
                son[p][c]=nq;
                p=fail[p];
            }
        }
    }
}

// 链式前向星存储fail树
struct node{
    LL to,next;
}dis[maxn]; 
LL num,head[maxn];

inline void Add(LL u,LL v){
    dis[++num]=(node){v,head[u]},head[u]=num;
}

// DFS处理fail树，标记只属于一个名字的节点
void Dfs(LL u){
    for(LL i=head[u];i;i=dis[i].next)
        Dfs(dis[i].to);
    for(LL i=head[u];i;i=dis[i].next){
        LL v(dis[i].to);
        if(mark[v]==-1||mark[u]!=mark[v]){  // 若子节点不属于同一名字或已被标记为公共
            mark[u]=-1;  // 标记当前节点为公共节点
            break;
        }
    }
}

int main(){
    scanf("%d",&n);  // 修正输入读取
    for(LL i=1;i<=n;++i){
        cin>>s;
        lst=1;
        for(LL j=0,Len=s.length();j<Len;++j)
            Insert(s[j]-'a',i);  // 插入每个字符并构建后缀自动机
    }
    for(LL i=1;i<=nod;++i)
        Add(fail[i],i);  // 构建fail树
    Dfs(1);  // 处理父链关系
    for(LL i=1;i<=nod;++i)
        if(mark[i]!=-1)  // 累加只属于一个名字的节点贡献
            ans[mark[i]]+=len[i]-len[fail[i]];
    for(LL i=1;i<=n;++i)
        printf("%d\n",ans[i]);  // 输出每头奶牛的独特性因子
    return 0;
}

复杂度分析

时间复杂度：构建广义后缀自动机的时间复杂度为 $O (ΣL)$ ，其中 $ΣL$ 是所有名字的总长度。DFS 处理 fail 树的时间复杂度为 $O (nod)$ ，其中 $nod$ 是后缀自动机的节点数，最坏情况下为 $O (ΣL)$。因此，总的时间复杂度为 $O (ΣL)$。
空间复杂度：主要用于存储后缀自动机的节点和转移边，空间复杂度为 $O (ΣL)$。