RT.

一直WA成16 QAQ

#include <bits/stdc++.h>
#define ll long long
#define Mid ((L+R)>>1)
using namespace std;
typedef pair<int,int> pii;
inline int read(){
	char c;int x=0;int b=1;do{c=getchar();if(c==45)b=-1;}while(c>57||c<48);
	do x=x*10+c-48,c=getchar();while(c<=57&&c>=48);x*=b;return x;
}
const int maxn=500010;
struct node{
	int c[27],sum,is,len,link;
}a[maxn];
struct trie{
	int son[27],last,b;
}t[maxn*20];int cnt2=1;
int cnt=1,g[maxn],Q[maxn],top;
int insert(int now,char c,int s){
	int S=c-'a'+1,p=++cnt;
	a[p].len=a[now].len+1;a[p].is=s;
	while(now && !a[now].c[S])a[now].c[S]=p,now=a[now].link;
	if(!now)a[p].link=1;
	else{
		int to=a[now].c[S];
		if(a[to].len-a[now].len==1)a[p].link=to;
		else{
			int clone=++cnt;
			a[clone]=a[to];
			a[clone].is=0;
			a[clone].len=a[now].len+1;
			while(now && a[now].c[s]==to)a[now].c[s]=clone,now=a[now].link;
			a[p].link=a[to].link=clone;
		}
	}return p;
}
string S[maxn];
void INSERT(int x){
	int now=1,fa=-1;
	for(int i=0;i<S[x].size();i++){
		int s=S[x][i]-'a'+1;fa=now;
		//cout<<"INSERTing... now="<<now<<endl;
		if(!t[now].son[s])t[now].son[s]=++cnt2;
		now=t[now].son[s];
		if(!t[now].last)t[now].last=insert(t[fa].last,S[x][i],x),t[now].b=x;
		else{a[t[now].last].is=-1;}
	}
}
int i,j,k,n,m,last;ll ans[maxn];
int main() {
	freopen("P4081.in","r",stdin);
	freopen("P4081.out","w",stdout);
	cin>>n;t[1].last=1;
	for(i=1;i<=n;i++)cin>>S[i];
	for(i=1;i<=n;i++)INSERT(i);
	for(i=1;i<=cnt;i++)g[a[i].link]++;
	for(i=1;i<=cnt;i++)if(!g[i])Q[++top]=i;
	while(top){
		int now=Q[top--];
		if(!now)continue;
		if(a[now].is>0)ans[a[now].is]+=a[now].len-a[a[now].link].len;
		if(a[a[now].link].is!=a[now].is)a[a[now].link].is=(a[a[now].link].is?-1:a[now].is);
		g[a[now].link]--;if(!g[a[now].link])Q[++top]=a[now].link;
	}
	for(i=1;i<=n;i++)printf("%d\n",ans[i]);
	cerr << 1.0*clock()/CLOCKS_PER_SEC << endl;
	return 0;
}