BZOJ4458: GTY的OJ-白红宇

BZOJ4458: GTY的OJ

阅读量：5135 次

发布时间：2019-06-13

本文共 3386 字，大约阅读时间需要 11 分钟。

题解:上树的超级钢琴我们考虑dfs的时候直接由父亲转移而来那么我们对于每个节点则维护是这点到根路径上的分布情况那么转化为序列上的问题这也就和超级钢琴本质上是一样的了

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define mp make_pair#define pb push_back#define pii pair
               
                #define link(x) for(edge *j=h[x];j;j=j->next)#define inc(i,l,r) for(int i=l;i<=r;i++)#define dec(i,r,l) for(int i=r;i>=l;i--)const int MAXN=5e5+10;const double eps=1e-8;#define ll long longconst ll inf=1e18;using namespace std;struct edge{int t;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}ll read(){ ll x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f;}typedef struct Node{ int id,l,r,pos;ll ans; friend bool operator <(Node aa,Node bb){return aa.ans
                
                 
                  que;typedef struct node{ int l,r,pos;ll sum,flag;}node;node d[MAXN*31];int cnt,n,m,L,R,dep[MAXN],rt[MAXN],a[MAXN];void up(int x,int l,int r){ d[x].sum=d[d[x].l].sum+d[x].flag,d[x].pos=d[d[x].l].pos; if(!d[x].pos)d[x].pos=l; if(d[d[x].r].sum+d[x].flag>d[x].sum){d[x].sum=d[d[x].r].sum+d[x].flag,d[x].pos=d[d[x].r].pos; if(!d[x].pos)d[x].pos=r; }}void update(int &x,int y,int l,int r,int ql,int qr,int vul){ x=++cnt;d[x]=d[y]; if(!d[x].pos)d[x].pos=l; if(ql<=l&&r<=qr){d[x].sum+=vul;d[x].flag+=vul;return ;} int mid=(l+r)>>1; if(ql<=mid)update(d[x].l,d[y].l,l,mid,ql,qr,vul); if(qr>mid)update(d[x].r,d[y].r,mid+1,r,ql,qr,vul); up(x,l,r);}ll maxx;int id;void querty(int x,int l,int r,int ql,int qr,ll tag){ if(!x){ if(tag>maxx)maxx=tag,id=l; return ; } if(ql<=l&&r<=qr){ if(d[x].sum+tag>maxx)maxx=d[x].sum+tag,id=d[x].pos; return ; } int mid=(l+r)>>1; if(ql<=mid)querty(d[x].l,l,mid,ql,qr,tag+d[x].flag); if(qr>mid)querty(d[x].r,mid+1,r,ql,qr,tag+d[x].flag);}void dfs(int x,int deep,int fa){ dep[x]=deep+1;update(rt[x],rt[fa],1,n,1,dep[x],a[x]); link(x){ if(j->t!=fa){ dfs(j->t,deep+1,x); } }}void slove(){ inc(i,1,n){ if(dep[i]
                  
                   t.l)maxx=-inf,querty(rt[t.id],1,n,t.l,t.pos-1,0),que.push((Node){t.id,t.l,t.pos-1,id,maxx}); if(t.pos

4458: GTY的OJ

Time Limit: 40 Sec Memory Limit: 512 MB

Submit: 167 Solved: 72

[][][]

Description

身为IOI金牌的gtyzs有自己的一个OJ，名曰GOJ。GOJ上的题目可谓是高质量而又经典，他在他的OJ里面定义了一个树形的分类目录，且两个相同级别的目录是不会重叠的。比如图论的大目录下可能分为最短路，最小生成树，网络流等低一级的分类目录，这些目录下可能还有更低一级的目录，以此类推。现在gtyzs接到了一个任务，要他为SDTSC出题。他准备在自己的OJ题库中找出M道题作为SDTSC的试题，而他深知SDTSC的童鞋们个个都是神犇，所以gtyzs认为自己出的这M道题中，每道题都应该属于不少于L种分类目录；可他又怕自己的题没有人会做，所以每道题也应该属于不超过R种分类目录，并且这些分类目录应该是连续的，不能出现断层。对了，最重要的是，不存在一道题，它属于两个分类目录且这两个目录不是包含关系。（比如不存在一道题它既是一道DP题，又是一道网络流题）gtyzs怕被骂，所以他希望不存在任意的一对题目(u,v)，使得u所属的分类目录与v完全相同。举例来说，gtyzs不能出两道同样的都是动态规划，背包的题，但是却可以出一道属于动态规划，背包和01背包的题和一道属于背包，01背包的题，当然也可以出一个属于图论的题和一个属于数论的题。（注意：一道题所属的分类目录不一定从根开始，如加粗部分所示）

为了让自己的题目变得更加靠谱，他给每一个分类目录都定了一个靠谱值ai，这个值可正可负。一道题的靠谱度为其从属的分类目录靠谱值的加和。我们假设动态规划的靠谱值为10，插头DP的靠谱值为－5，则一道动态规划插头DP的题的靠谱值就是5。gtyzs希望自己出的这M道题，在满足上述前提条件下，靠谱度总和最大。gtyzs当然会做啦，于是你就看到了这个题。

Input

输入的第一行是一个正整数N，代表分类目录的总数。

接下来的一行，共N个正整数，第i个正整数为fi，表示分类目录i被fi所包含。保证一个分类目录只会被一个分类目录所包含，且包含关系不存在环。特别的，fi＝0表示它是根节点，我们保证这样的点只存在一个。

接下来的一行，共N个整数，第i个数表示ai。

最后一行，三个正整数M,L,R。

对于100%的数据，1≤N≤500,000，1≤M≤500,000，|ai|≤2,000。保证输入数据有解。

为了方便，所有的测试数据中都有f1＝0，且对于任意的i∈[2,N]，有fi<i。

Output

一行一个整数，表示最大的靠谱度。

Sample Input

0 1 1 2 2 3 3

2 3 4 1 2 3 4

3 3 3

Sample Output

转载于:https://www.cnblogs.com/wang9897/p/9635014.html

你可能感兴趣的文章