T1.回文树裸题。
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';}
return x*f;
} int cnt=;
int f[],l[],p[];
int c[][];
char s[]; int main()
{
freopen("palindrome.in","r",stdin);
freopen("palindrome.out","w",stdout);
scanf("%s",s+);
f[]=;l[++cnt]=-;
for(int i=,j=;s[i];++i)
{
while(s[i]!=s[i-l[j]-]) j=f[j];
if(!c[j][s[i]-'a'])
{
l[++cnt]=l[j]+;
int k=f[j];
while(s[i]!=s[i-l[k]-])
k=f[k];
f[cnt]=c[k][s[i]-'a'];
c[j][s[i]-'a']=cnt;
}
j=c[j][s[i]-'a'];
++p[j];
}
ll ans=;
for(int i=cnt;i>;i--)
{
ans=max(ans,1ll*p[i]*l[i]);
p[f[i]]+=p[i];
}
cout<<ans;
return ;
}
T2.斜率优化
f[i]=max(f[j]+s[j]*(s[i]-s[j]))
令g[i]=f[i]-s[i]^2
j比k优 那么g[j]+s[i]s[j]>g[k]+s[i][k]
g[j]-g[k]>s[i](s[k]-s[j])
g[j]-g[k]/(s[j]-s[k])<-s[i]
所以维护队列上凸即可
#include<iostream>
#include<cstdio>
#include<queue>
#define MAXN 100000
#include<cstring>
#define ll long long
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} int n,k;
int from[][MAXN+];
ll f[MAXN+];
ll s[MAXN+];
ll g[][MAXN+];
int q[MAXN+];
int top=,tail=; ll get(int pre,int x,int t)
{
while(top-tail>=&&(g[pre][q[tail]]-g[pre][q[tail+]])<s[x]*(s[q[tail+]]-s[q[tail]]))
++tail;
from[t][x]=q[tail];
return g[pre][q[tail]]+s[q[tail]]*s[x];
}; void ins(int t,int k)
{
while(top-tail>=)
{
int i=q[top-],j=q[top];
if((g[t][k]-g[t][j])*(s[i]-s[j])<(g[t][j]-g[t][i])*(s[j]-s[k])) top--;
else break;
}
q[++top]=k;
} int main()
{
//freopen("sequence.in","r",stdin);
//freopen("sequence.out","w",stdout);
n=read();k=read();
for(int i=;i<=n;i++)
{
s[i]=read();s[i]+=s[i-];
}
int pre=,nown=;
for(int i=;i<=n;i++) g[pre][i]=-(s[i]*s[i]);
for(int l=;l<=k+;l++)
{
memset(f,,sizeof(f));top=;tail=;
memset(g[nown],,sizeof(g[nown]));
ins(pre,l-);
for(int i=l;i<=n;i++)
{
f[i]=get(pre,i,l);
g[nown][i]=f[i]-(s[i]*s[i]);
if(s[i]!=s[i-])ins(pre,i);
//printf("%d %d %d %I64d\n",l,i,from[l][i],f[i]);
}
nown=-nown;
pre=-pre;
}
printf("%lld\n",f[n]);
return ;
}
T3.
树形dp，把根节点作为第一个存在的点，那么每一段蓝线总是 爷爷-爸爸-点 的形式。
所以用f1表示一个点作为中间的点的最大值，f2表示一个点不是中间点的最大答案。
树形dp之后O(1)换根
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define MAXN 200000
#define INF 2000000000
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} ll ans=;
int n,cnt=;
ll f[MAXN+],f2[MAXN+];
int mx[MAXN+],mx2[MAXN+],from[MAXN+],from2[MAXN+];
int fa[MAXN+],head[MAXN+],p[MAXN+]; struct edge{
int to,next,w;
}e[MAXN*+]; void ins(int f,int t,int w)
{
e[++cnt].next=head[f];
head[f]=cnt;
e[cnt].to=t;
e[cnt].w=w;
} void renew(int x,int t,int f)
{
//cout<<"ins"<<x<<" "<<t<<" "<<f<<endl;
if(t>mx[x])
{
from2[x]=from[x];
mx2[x]=mx[x];
mx[x]=t;
from[x]=f;
}
else if(t>mx2[x])
{
mx2[x]=t;
from2[x]=f;
}
} void dfs(int x,int pre,int father)
{
fa[x]=father;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(v!=fa[x])
{
dfs(v,e[i].w,x);f2[x]+=max(f[v],f2[v]);
renew(x,e[i].w+f2[v]-max(f[v],f2[v]),v);
}
}
f[x]=f2[x]+mx[x]+pre;
if(f[x]<) f[x]=;
//cout<<x<<" "<<f[x]<<" "<<f2[x]<<endl;
} void solve(int x)
{
if(fa[x])
{
int v=fa[x];f2[x]+=max(f[v],f2[v]);
renew(x,p[x]+f2[v]-max(f[v],f2[v]),v);
}
ans=max(ans,f2[x]);f[x]=f2[x]+mx[x];
//cout<<"solve"<<x<<" "<<f2[x]<<" "<<f[x]<<endl;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(v!=fa[x])
{
ll t2=max(f[v],f2[v]);
f[x]+=e[i].w-t2;
if(from[x]==v) f[x]=f[x]-mx[x]+mx2[x];
f2[x]-=t2;p[v]=e[i].w;
solve(v);
f2[x]+=t2;
f[x]=f2[x]+mx[x];
}
}
} int main()
{
freopen("beads.in","r",stdin);
freopen("beads.out","w",stdout);
n=read();
for(int i=;i<n;i++)
{
int u=read(),v=read(),w=read();
ins(u,v,w);ins(v,u,w);
}
for(int i=;i<=n;i++) mx[i]=mx2[i]=-INF;
dfs(,,);
solve();
cout<<ans;
return ;
}