欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【JZOJ5336】【NOIP2017提高A组模拟8.24】提米树

程序员文章站 2024-02-11 23:28:10
...

Description

【JZOJ5336】【NOIP2017提高A组模拟8.24】提米树

Data Constraint

【JZOJ5336】【NOIP2017提高A组模拟8.24】提米树

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);
}