【JZOJ5336】【NOIP2017提高A组模拟8.24】提米树
程序员文章站
2024-02-11 23:28:10
...
Description
Data Constraint
Solution
我们可以用dp解决。设dp[i]表示前i个节点的最优值。我们发现一对节点(x,y)(x的dfs序小于y的dfs序)可以形成相邻叶子当且仅当x处于其lca的儿子u的右链上,y处于lca的儿子v的左链上,且u,v相邻u在v的左方。我们将每一条右链存下,对于每个节点查找其对应右链的答案。这样是O(N^2)的。
我们发现没一个左链上的点顺序往下的同时,我们若维护最大值在左链上,右链的范围是单调递增的,我们可以维护一个指针即可查询答案。最大值在右边同理。时间复杂度O(N)。在这里很想吐槽数据开10^5,这TM根本在本机上没法调,还要我专门改成bfs来调试!!!
Code
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=3e5+5;
int first[maxn],last[maxn],next[maxn],a[maxn],f[maxn],b[maxn],size[maxn],fa[maxn];
int first1[maxn],last1[maxn],next1[maxn],top[maxn],dfn[maxn],d[maxn],g[maxn],g1[maxn];
int n,i,t,j,k,l,x,y,z,num,num1,ln,ans,mx,mx1;
void lian(int x,int y){
last[++num]=y;next[num]=first[x];first[x]=num;
}
void lian1(int x,int y){
last1[++num1]=y;next1[num1]=first1[x];first1[x]=num1;
}
void dg(int x,int y){
int t;dfn[x]=++num;g1[num]=x;
if (!y) f[x]=a[x];size[x]=1;
for (t=first[x];t;t=next[t]){
fa[last[t]]=x;
if (size[x]>1)top[last[t]]=last[t],dg(last[t],num);
else top[last[t]]=top[x],dg(last[t],y);
size[x]+=size[last[t]];
}
lian1(dfn[x]+size[x]-1,x);
}
int main(){
// freopen("data.in","r",stdin);freopen("data.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%d",&a[i]);
scanf("%d",&t);
for (j=1;j<=t;j++)scanf("%d",&b[t-j+1]);
for (j=1;j<=t;j++)lian(i,b[j]);
}
num=0;top[1]=1;
dg(1,0);
k=1;top[n+1]=n+1;
for (i=2;i<=n+1;i++)
if (top[g1[i]]==g1[i]){
x=dfn[g1[k]]-1;
if (!x){
k=i;continue;
}
d[0]=0;
for (t=first1[x];t;t=next1[t])d[++d[0]]=last1[t];d[d[0]+1]=0;
t=0;mx1=-1e9;mx=b[0]=a[fa[g1[k]]];
for (j=1;j<=d[0];j++)b[j]=max(b[j-1],a[d[j]]);g[d[0]+1]=g[d[0]+2]=-2e9;
for (j=d[0];j>=1;j--)g[j]=max(g[j+1],f[d[j]]-b[j-1]);
for (j=k;j<i;j++){
while (b[t]<=mx && t<d[0]) mx1=max(mx1,f[d[++t]]);
f[g1[j]]=max(mx1+a[g1[j]]-mx,g[t+1]+a[g1[j]]);
mx=max(mx,a[g1[j]]);
}
k=i;
}
ans=0;
for (i=1;i<=n;i++)
if (dfn[i]+size[i]==n+1) ans=max(ans,f[i]);
printf("%d\n",ans);
}