C++ 解法, 执行用时: 63ms, 内存消耗: 6996K, 提交时间: 2021-12-12 14:28:03

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int N = 100010;

int v[N];
int nxt[N], fa[N], siz[N];
vector<int> edge[N];

struct node
{
	int x,siz;
	long long w;
	bool operator<(const node b)const{return w*b.siz<b.w*siz;}
};

priority_queue<node> q;
long long ans;

int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void push(int x)
{
	q.push(node{x,siz[x],v[x]});
}

void merge(int f,int x)
{
	ans+=1ll*siz[f]*v[x];
//	cout<<"merge "<<f<<" "<<x<<" "<<ans<<endl;
	v[f]+=v[x];
	siz[f]+=siz[x];
}

int main()
{
	int n;
	string s;
	int i, j;
	int x, f;
	
	cin >> n;
	cin >> s;
	for(i = 1; i <= n; i ++)
		cin >> v[i];
	
	j=nxt[0]=-1;
	i=0;
	while(i<n){
		while(-1!=j && s[i]!=s[j])j=nxt[j];
		nxt[++i]=++j;
	}
	
//	for(i=1;i<=n;i++)cout<<nxt[i]<<' ';cout<<endl;
	
	for(i = 1, ans = 0; i <= n; i ++)
	{
		fa[i] = i;
		siz[i] = 1;
		ans += v[i];
		push(i);
	}
	
//	cout<<ans<<endl;

	while(!q.empty())
	{
		x=q.top().x;
//		cout<<x<<endl;
		q.pop();
		if(x!=find(x))continue;
		x=find(x);
		fa[x]=f=find(nxt[x]);
		merge(f,x);
		if(f)push(f);
	}
    
    cout << ans << endl;
	
	return 0;
}