记录编号	326535	评测结果	AAAAAAAAAA
题目名称	拯救紫萱学姐	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	1.551 s
提交时间	2016-10-21 09:21:13	内存使用	58.46 MiB

#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
#define file(x) "savemzx."#x
using std::set;
using std::max;
typedef long long ll;
const int MAXN=1000010;
int n,nxt[MAXN],unxt[MAXN];
ll ans,dis[MAXN];
char s[MAXN];
struct EDGE{int u,v;ll w;}st[MAXN<<1];
int hed[MAXN],gnxt[MAXN<<1],sz;
void _add(int u,int v,ll w){
	st[++sz].u=u,st[sz].v=v,st[sz].w=w;
	gnxt[sz]=hed[u],hed[u]=sz;
}
void add(int u,int v,ll w){
	_add(u,v,w);
	_add(v,u,w);
}
ll nd;
void dfs(int u,int fa){
	dis[u]=nd;
	for(int e=hed[u];e;e=gnxt[e]) if(st[e].v!=fa){
		nd+=st[e].w;
		dfs(st[e].v,u);
		nd-=st[e].w;
	}
}
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=2;i<=n;i++){
		int p=nxt[i-1];
		while(p&&s[p+1]!=s[i]) p=nxt[p];
		if(s[i]==s[p+1]) p++;
		nxt[i]=p;
	}
	for(int i=n;i;i--){
		ll p=nxt[i];
		add(i,p,(i-p)*(i-p));
	}
	dfs(1,-1);
	int u=0;
	for(int i=0;i<=n;i++) if(dis[i]>dis[u]) u=i;
	dfs(u,-1);
	int v=0;
	for(int i=0;i<=n;i++) if(dis[i]>dis[v]) v=i;
	printf("%lld",dis[v]);
}