蒟蒻求助,第7个点WA了
查看原帖
蒟蒻求助,第7个点WA了
1038510
Y_X_C楼主2023/9/10 21:17
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define MAXN 510000
using namespace std;
int n,len,tot;
char c[MAXN];
struct trie
{
	int ch[26];
	int vis;
}tr[MAXN];
vector<int>v[MAXN];
void build()
{
	int p=1;
	for(int i=0;i<len;i++)
	{
		if(!tr[p].ch[c[i]-'a'])
			tr[p].ch[c[i]-'a']=++tot;
		p=tr[p].ch[c[i]-'a'];  
	}
	tr[p].vis++;
}
bool flag;
void dfs1(int p,int last)
{
	if(tr[p].vis)
	{
	  v[last].push_back(p);
	  for(int i=0;i<26;i++)
	  {
		if(tr[p].ch[i])
		  dfs1(tr[p].ch[i],p);
	  }
    }
    else
    {
      for(int i=0;i<26;i++)
	  {
		if(tr[p].ch[i])
		  dfs1(tr[p].ch[i],last);
	  }	
	}
}
int size[MAXN];
bool cmp(int a,int b)
{
	return size[a]<size[b];
}
void dfs2(int p)
{
   size[p]=1;
   for(int i=0;i<v[p].size();i++)
	{
		dfs2(v[p][i]);
		size[p]+=size[v[p][i]];
	}
	sort(v[p].begin(),v[p].end(),cmp);	
}
int ans,dfn[MAXN];
void dfs_ans(int p,int from)
{
   dfn[p]=++dfn[0];
   ans+=dfn[p]-dfn[from];
   for(int i=0;i<v[p].size();i++)
	  dfs_ans(v[p][i],p);
}
int main()
{
	scanf("%d",&n);
	tot=1;
	for(int i=1;i<=n;i++)
	{
		cin>>c;
		len=strlen(c);
		reverse(c,c+len);
		build();
	}
	dfs1(1,1);
	dfs2(1);
	dfs_ans(1,1);
	printf("%d",ans);
	return 0;
}
2023/9/10 21:17
加载中...